BLeak: Automatically Debugging Memory Leaks in Web Applications

and this is joint work with my adviser Henry Berger so before I dive into memory leaks on the web I want to ask a philosophical question what are memory leaks anyway you might think that the answer is obvious but it's actually surprisingly subtle let's consider manual memory management in a language like C or C++ when a developer needs some precious valuable memory they call malloc and if the program no longer needs the memory the developer needs to call free to let it go sometimes the program has memory that looks valuable and in use but it's actually worthless like an ineffective cache that it just doesn't need and this can also be safely freed without impacting the program it's up to the developer to determine when one memory becomes garbage or worthless and to call free to release it if the developer doesn't free some garbage or some worthless memory it sticks around and if this continues to happen the programs heap becomes like an episode of Hoarders in manual memory management land failing to free garbage or worthless memory causes memory leaks on automatic memory management ensures that certain kinds of leaks can't happen memory that is valuable to the program is reachable and the garbage collector keeps reachable memory around when the memory becomes unreachable and starts to pile up the garbage collector automatically throws it all away ensuring that garbage does not stick around but what about worthless memory if garbage is automatically collected can a program have worthless memory it turns out yes it can automatic memory management does not solve the problem of leaks caused by worthless memory just because memory is reachable does not mean that it is valuable as a result worthless memory can pile up in a garbage collected program with no problem one approach for identifying worthless memory is staleness tracking objects become fresh when they are used and eventually they become stale if they have not been accessed recently still objects are marked as potential memory leaks another approach to locate worthless memory is growth analysis growth analysis locates objects that grow and count or in size assuming that continually growing things are unintentional and likely to be leaks neither of these approaches is a silver bullet for finding memory leaks in the presence of automatic memory management worthless memory can be reachable and accessed frequently by an application a staleness based approach will not find those leaking objects also object growth does not always indicate a leak some growth is desirable such as caches gross spit growth based approaches may incorrectly mark those objects as leaks what we really want is a semantic space definition of a memory weak an object source is leaking if deleting some of the objects does not impact the program's behavior which indicates that the objects are in fact worthless and if it retains an unbounded number of objects over time however there's a problem with this definition how can we tell that the number of objects is actually unbounded and that they have no impact on the program's behavior what we need is an Oracle this is the oracle at delphi an oracle promises to identify leak object sources and say hey what's with all this smoke get rid of it it's not needed it's worthless in order to find this Oracle at Delphi we're going to need to travel the Delphi in Greece the neighborhood's not quite what it used to be but maybe we can find her maybe she's still around somewhere and if we are to travel to Greece we're going to find a place to stay so I'll head to one of my favorite websites airbnb.com and search for Delphi after browsing for a while though I noticed something odd the web page becomes slow and unresponsive and it takes a long time to load pages and eventually the browser crashes because it's out of memory Airbnb appears to have them and this is a true story if this has actually happened to us and we discovered it in the course of this work and what we've also discovered firsthand in this work is that it's not just Airbnb that is suffering from memory leaks plenty of other websites and the libraries that they use suffer from memory leaks that degrade browser responsiveness over time and in fact over 99% of google chrome crashes on low-end Android smartphones are due to memory issues these problems are not just a matter of speed they can prevent visitors from spending time on a website today the process of debugging these memory leaks is arduous developers typically examine and compare heap snapshots that display the live objects of the program here's a heap snapshot from Airbnb com two of these object types are internal browser objects that website code does not directly manage and they're unhelpful for a web developer the other two contained every array in the program and every object of an unnamed type and unnamed objects happen often as javascript is dynamically typed and if I expand the view a bit I'll find xn and other random names that mean very little to the developer since the source code is of the web page is minified and obfuscated to reduce the size of the JavaScript code what is not evident in this view is where the worthless objects are and where the heap is growing which heap items are unneeded and can be deleted identifying worthless leaking objects is a huge challenge even for seasoned developers a Google developer closed a Google Maps memory leak in issue in their bug tracker that over 100 developers voted on and that's easily among one of the highest ranked bug reports and they did that because it was infeasible to debug the leak things are looking quite bleak for debugging memory leaks in web applications however there is hope most modern single page web applications such as Airbnb Gmail weather com frequently returned to the same visual state and by visual state I mean a literal view that the application presents to the user typically corresponding to a specific screen on Airbnb I can click between the listing of homes for rent and a list of recommendations tailored specifically for me and these screens are the core output of a web application if the applications heap exhibits sustained growth after each visit to a specific screen then the application likely has a memory leak in other words growth between visits to the same screen is a strong indicator of a week and this growth can be used as an Oracle to identify worthless memory this insight is central to bleak an automatic memory leak debugger for web applications weak uses growth between round trips to the same visual state as an Oracle to identify leaking objects because we have this Oracle leak exhibits high precision on a corpus of real production web applications over 90% of the leaks reported are true leaks the leak step league finds also have high impact we've found large leaks in production web applications leak also identifies the source code that is directly responsible for causing each week which dramatically simplifies the process of fixing them to use bleak a developer must write a short input script of about 40 lines of code which I will describe momentarily and this script drives the application in e loop through distinct visual States this is thus all input tube leak the rest of the process is completely automatic this is the input script that I wrote to run Bleek on air B&B I don't expect any of you to read this but I want to note that it's only 17 lines of code and this script forms a simple visual state machine where each visual state has a check and a next function let's briefly look at one of these states this is the visual state corresponding to the Airbnb page with recommendations for me the check function returns true when the application has finished drawing the visual state in this case it's quite simple it very is that the for you link at the top of the webpage is selected the next function transitions the application into the next visual state so for Airbnb it clicks on the homes link in the top navigation and that set zooming back out Bleek executes the input script in the following manner bleak first waits for the application to load and display the fur you screen then it transitions to the home screen bleak waits for the application to finish displaying the home screen before transitioning to the for you screen and then with this the loop is closed and now we have a way to run the application in a loop and as mentioned before the developer only needs to provide that input script oblique and the rest of the process is completely automatic bleek loads the application in chrome and commands the browser via the remote debugging protocol Chrome has configured to talk to a bleak controlled proxy which performs JavaScript rewriting needed for memory leak debugging and with this architecture we can diagnose memory leaks and unmodified web applications in production that we don't control just like Airbnb using bleak I have found reported and fixed over 50 memory leaks in a wide variety of popular web applications and libraries including Airbnb jQuery and angularjs all these leaks were completely unknown to us and to application developers leak identifies memory leaks by looking for growing objects in the heap between round trips to a visual state I want to stress that a heap graph alone does not make memory leaks obvious here's the heap graph for about blank which is a blank web page it has tens of thousands of nodes and edges and these all correspond to internal browser objects the air grunting what the heap graph for Airbnb looks like it looks like this so this is the actual screenshot of the graphing program Getty struggling to display of the heap graph there are over 800,000 nodes and four million edges in the heap graph and we have no idea which are responsible for leaks so for the purpose of this presentation I'm going to dramatically simplify the graph which will give away a major week that we found and while I do that keep this image in mind because leaking objects are far from obvious so the first visit to air BnB x' home screen yields a heap graph like the following using the developer provided input script Bleek runs the application in a loop back to the home screen and takes another heap snapshot now three objects have grown since the last visit bleak marks these as potential memory leak routes bleak repeats this process multiple times typically for a total of eight round trips to filter out objects that grow to a fixed size at the end of this process Bleek identifies a set of leak routes which are responsible for leaking memory including these three large map objects which we had no idea where we can going into this also in that non simplified heap graph each of these map is actually a very large sub graph of many small objects so this leak again is very far from obvious in a in a heap graph so now that leak has identified growing objects these these leak routes it needs to rank them by importance so developers can spend their time fixing memory leaks that actually matter and while I am only showing three leak routes on this slide there may be many more for the developer to prioritize and in fact we found 32 distinctly Kreutz on airbnb.com one possible ranking metric is retained size which is the quantity of memory that would be collected if a leak route were garbage collected this is a standard metric that many tools use the global variables window and document are not garbage collectable so they're not relevant to the metric the problem with this metric is that objects shared between leak routes like these very large map objects are not captured by this metric fixing a single leak root will knock garbage collect them and so no leak root gets the credit for them as a result retained size in this case actually ranks the history leak root which is an array of strings above the eventlistener leaks which collectively retain multiple megabytes of map memory essentially retained size misrepresents the impact of memory leaks bleak uses a new metric that we call leak share to measure the impact of memory leaks leak share splits the credit for objects shared between leak roots and the algorithm is conceptually simple first we share ignores objects that are reachable from non leak roots because these are not leaked objects second for each remaining object leak share counts the number of leak routes that retain it in this example each map is retained by to leak roots while everything else is only retained by one third week share splits the credit for each object evenly between the leak roots that retain it the end result is that the event listener leaks event listener lease lists which leak large map objects are correctly ranked above the history array we share focuses developer effort on memory leaks that provide the biggest return on investment meaning the developer spends less time developing fewer fixes that free more memory to diagnose the memory leaks bleak reruns the application in a loop and collect stack traces when the leak roots grow leak collects a stack trace when the application adds an item to a leak root causing it to grow and if that item is later removed bleek removes the stack trace as well because the application has responsibly managed its memory and to collect these stack traces bleak uses JavaScript reflection and program transformations and these stack traces point directly to the code responsible for each memory leak at the end of a bleak run bleak produces an interactive report that describes its findings on the slide is the report that leak produced for airbnb.com the production website during our evaluation let's take a closer look at the top of the report bleak quantifies the amount of live heap growth that had observed at Airbnb calm it appears that Airbnb is live heap size increases by a whole megabyte every time we return to the home screen true story below the heap size graph bleak lists the weak roots found ranked by leaks share fixing the top most leaks should provide the greatest return on investment and if we click on one of these lead groups the panel expands to reveal a list of stack traces that were recorded when the weak root grew these stack traces directly identify the code responsible for growing that leak root and thus for the memory leak next to the leak root listing is the complete JavaScript source code to the web application collected during Bleek's run the source code viewer comes complete with a pretty print function which makes minified javascript somewhat readable just to give you an idea of the complexity of modern web apps Airbnb ships with over three megabytes of minified and obfuscated JavaScript and if you pretty print it it comes out to about a hundred and seventy-five thousand lines of code so finding memory leaks in this code base is like finding a needle in a haystack clicking on one of these stack frames and one of the stack traces like so causes the source viewer to jump to the line of code that the stack trace represents this is pretty small so let's zoom in a little bit this javascript statement highlighted in yellow inserts a new global resize of that listener every time we revisit Airbnb as home screen each of these event listeners retains a large map this leak can be fixed by adding an explicit cleanup handler to the Google Maps library that removes the resize of that listener prior to navigating to a new screen overall leak reported 32 leak routes for Airbnb comm and of these only two were false positives corresponding to objects that grow to a fixed size but we didn't observe it stopping the growth during eight runs using Bleek's output I was able to implement fixes for each of these leak route you these leaks and test them locally by injecting them into the web page using Bleek's proxy each of these fixes took about ten minutes to develop simply pointed directly to the code that was responsible and fixing all these leaks eliminated over a megabyte of heap growth per round-trip which reduced heap growth by eighty percent for this particular application guided by bleak I was able to develop a fix for the Google Maps memory leak and I provided the developers with all the information required to fix the bug and also happily provided many developers with workarounds for the bug and they're very happy with that we also ran bleak on a variety of other production web applications this line represents live heap size over round trips through a specific visual state with no leak fixes in place for each of these evaluation applications you can clearly see that all of these applications have memory leaks this dotted green line is the live heap size after fixing all of the leaks that leak reported we don't know how many leaks there are that bleak did not find but it's clear that fixing the leaks significantly decreased heap growth and in fact fixing Bleak reported leaks reduced heap growth by an average of 94% we believe that the core ideas in this work are useful beyond web applications and can be used to find memory leaks and other types of GUI applications such as mobile applications and native GUI applications we plan to explore this area in future work so I just told you about week an automatic memory leak debugger for web applications leak is open source and can be found at week - detector org thank you all for your attention [Applause] [Music] I'm Hannes working on v8 and Chrome mom the web is indeed leaking so this work is really impactful really cool thank you see that time have you thought about automating the input script because like you know many web pages have influenced crawling if you tend to scroll down for a while and go back up the build of a huge Dom tree or you could find like links and just walk through them and then use the back button to go back have you thought about automating that stuff completely yes I actually have there's been some great work in the PL community on synthesizing scripts for like web scraping for example which deal with a lot of the issues required to produce these input scripts so I think that that work is very harmonious with this work and that it might actually be feasible to automate creating them yeah I think that will be super useful for many developers who have no idea what a memory leak is completely agree thanks for the question yeah very cool work I have a very specific question and if you say you know look at the paper I'm happy with that too sure how do you efficiently compute the leak share metric if you have a very large graph it seems like that could be very expensive to compute it's only very expensive so it's it's basically order n as long as there's not significant overlap between all the of the weak roots so if in like the worst case if all the weak roots week the entire heap it might be pretty expensive in the worst case but that doesn't typically happen in practice so it yeah I haven't like had an issue with its scaling thanks thanks I'm talkin pretty interesting work I was wondering having looked at loads these leaks are they idiomatic and would there be any possibility for better design patterns or programming language features that could help avoid them in the first place yeah so there I think it has to do with with how how these applications are constructed in the first place because it's garbage collected people don't realize that in some case is you have to actually explicitly remove items after you insert them when you're transitioning to new web pages and while modern GUI frameworks like angular and react they have a notion of cleanup handlers developers aren't conditioned to actually create them so I don't really have an answer for how we could solve this from the programming languages standpoint but it is idiomatic and I think that's why we find it why it's so prevalent in the wild right now all right instead of sharing credit for for leaks did you consider providing a relation so that you could say you have to fix both of these you have to fix the leaks associated with both of these routes in order to recover this shared object I don't know how I would compute that efficiently because while most of the subgraph is shared there's always like a few objects that are only owned by a particularly group like the particular functions that are leaking the maps in a closure so I don't know how you would how you would efficiently compute those and present that in a meaningful manner for the developer I feel like more information would just be more confusing in that case but when you work three or thirty-two leaks presumably you didn't garner the the benefit from your effort until after you got say the second or third one when there was a shared object involved yeah so so right yes yeah like those maps would not be freed until you fixed all the leaks that that leaked them but programmatically looking at the heap I think it would be difficult to present that information to the user and in like an intuitive fashion that you have to fix these three leaks to free this much memory perhaps there is a way but I don't see it immediately I don't think it's immediately obvious to me but happy to chat further don't again thank you you [Applause]

Channel: PLDI 2018

Views: 2,008

Keywords:

Id: RzofyIvaY6A

Length: 23min 32sec (1412 seconds)

Published: Mon Jul 16 2018