Programming Languages & Software Engineering

Programming Languages & Software Engineering

Finding Errors in Multithreaded GUI Applications Sai Zhang University of Washington Joint work with: Hao Lu, Michael D. Ernst GUIs are everywhere in modern software 2 Multithreading in GUI applications A GUI Application UI thread UI event 1 UI event 2 3

The Single-GUI-Thread Rule All GUI objects must be exclusively accessed by the UI thread Required by: A GUI Application UI thread UI event 1 This non-UI thread must not access any GUI objects 4 Violation of the Single-GUI-Thread rule Triggers an Invalid Thread Access Error May abort the whole application SWT / Eclipse plugin

Android Swing 5 An Example Violation Do some computation, and update the UI. UI thread runTask() a non-UI thread button.setText(.) buttons event handler: public void runTask() { Runnable r = new Runnable() { public void run() {

//do some lengthy computation button.setText(Finished); } }; new thread(r).start(); } checkThread() Create a new, non-UI thread Access the button object to set text //GUI framework code public void setText(String) { checkThread(); ... } Trigger an invalid-thread-access-error 6

Invalid Thread Access Errors in practice Pervasive One of the top 3 bug categories in SWT [Shanmugam 2010] A Google search returns 11800+ entries (bug reports, FAQs, etc.) In Eclipse 2732 bug reports 156 confirmed bugs in 20+ projects, 40+ components Severe Often aborts the whole application Hard to debug Non-trivial effort to fix (e.g., 2 years to resolve one bug in Eclipse) 7 Why the Single-GUI-Thread Rule? Simpler programming No datarace nor deadlock on GUI objects Less overhead

No locking when accessing GUI objects A single event queue can dispatch UI events Easy event processing, program comprehension, and testing 8 Our Error Detection Technique Bugs Static Analyses 10 bugs 1. Call graph construction A GUI Application 2. Error detection Warnings

5 hours human inspection 3. Error filtering 9 applications from 4 supported GUI frameworks Less than 5 mins per application 20 warnings False Positives 10 false positives -Automated: no need for a test harness -General: instantiated it for 4 GUI frameworks: -Scalable: evaluated on 9 applications, over 1.4 M LOC with lib code -Practical: found 10 bugs with 10 false positives

9 UI thread Existing Solutions for this Problem runTask() a non-UI thread Testing Misses many corner cases in practice Stylized programming rules public void runTask() { Runnable r = new Runnable() { public void run() { //do some lengthy computation button.setText(Finished); } }; new thread(r).start();

asyncExec setText() Requiring Wrappers Display.asyncExec(new Runnable(){ public void run() { button.setText(Finished); } }; } - Unnecessary: if already on the UI thread Dangerous: may introduce new concurrency errors Results on 9 evaluation programs

#Warnings #Bugs Requiring Wrappers 6393 ? Our technique 20 10 Outline Problem Error detection technique Implementation Experiments Related work

Conclusion and future work 11 Terminology UI thread: a single special thread to handle UI events Non-UI thread: other threads UI-accessing method: a method whose execution may read or write a GUI object Safe UI method: message-passing methods to execute code on the UI thread A GUI Application UI-thread asyncExec(..) Non-UI thread UI-accessing method

void runTask() { ... button.setText(..); } Safe UI method 12 Assumptions Single UI thread Thread spawning: Every non-UI thread is (transitively) spawned by the UI thread A GUI Application UI-thread Non-UI thread 13

Problem formulation: call graph reachability An invalid thread access error occurs when: a non-UI thread invokes a UI-accessing method without going through a Safe UI method A reachability problem Source: non-UI thread spawning Sink: UI-accessing method button.setText() Non-UI thread spawning (source) Display.asycExec() UI-accessing method (sink) Thread.start() Safe UI method Other method entry

runTask() 14 Error detection algorithm 1. Construct a call graph for the tested program 2. Find paths from Thread.start() to UI-accessing methods without going through a safe UI method Non-UI thread spawning (i.e., Thread.start()) UI-accessing method A method-call chain as error report Safe UI method Other method entry 15

Reflection in Constructing Call Graphs Android Application:

S3dropbox 2,353 Sudoku Solver 3,555 Android applications SGTPuzzler 2,220 Mozilla Firefox 8,577 MyTracks 20,297 Total:

89, 273 Framework size: 1.4 MLOC 26 Experimental Procedural Run the error detection algorithm on each application 3 call graph construction algorithms RTA 0-CFA 1-CFA precision 2 configurations for Android applications with / without call graph enhancement (handle reflection + annotations for native methods)

Tool performance Less than 5 minutes per application Manual result inspection Spent 5 hours in total to check the output validity 27 Experimental Results Output 20 warnings, in which 10 are bugs (5 are new) Call graph algorithm # Warnings #Bugs RTA with enhancement 250 4

0-CFA with enhancement 136 6 1-CFA with enhancement 20 10 More precise call graph more bugs found 1-CFA found the most Call graph algorithm # Warnings #Bugs 1-CFA

19 8 1-CFA with enhancement 20 10 Call graph enhancement are useful (2 more bugs) 28 Comparing graph search strategies Our technique uses BFS, compare it with alternatives Strategies #Warnings #Bugs

BFS 20 10 Multi-source BFS 20 8 DFS 19 9 Exhaustive search 0 (explored 5,100,000,000+ non-cyclic paths in an hour)

0 Observations from our subject programs Multi-source BFS omits bugs DFS searches deeper, and returns longer paths (more likely to be invalid, due to the conservative call graph) Exhaustive search is sound but infeasible in practice 29 Evaluating error filters 70000 60000 60610 Sound Filters: F1: remove lexically subsumed reports Column2 50000

40000 40440 39753 F2: remove annotated reports 37414 Heuristic Filters: F3: remove specific library calls 30000 F4: merge common heads 20000 F5: merge common tails 10000 0 110

20 30 Experimental conclusion Our technique: Finds real invalid-thread-access errors Detects more errors as the call graph precision increases Uses BFS to find more errors than other search strategies Reduces likely invalid reports via 5 error filters 31 Outline Problem Error detection technique Implementation Experiments Related work Conclusion and future work

32 Related Work Analyzing and testing GUI applications Guitar [Memon 00], Stabilizer [Michail 05], Julia [Payet 11] Focus on test generation, error predication, and code verification; but does not support finding invalid thread access errors Finding bugs in multithreaded programs Eraser [Savage 97], Chord [Naik 05], Goldilocks [Elmas 07], FastTrack [Flanagan 09] Different goals (dataraces + deadlocks), algorithms, and, abstractions Call graph construction algorithms RTA [Bacon 97], k-CFA [Might 10], TamiFlex [Bodden 11] Does not support reflection, or need dynamic information 33 Outline Problem Error detection technique Implementation

Experiments Related work Conclusion and future work 34 Future Work Incorporate dynamic and symbolic analysis Filter out infeasible paths Identify more entry points Automatically fix the invalid-thread-access errors Counterexample-guided reasoning Heuristic reasoning Unit testing of multithreaded GUI applications Test abstraction Event simulation 35 Contributions

A general technique to find invalid thread access errors Formulate error detection as a call graph reachability problem A tool implementation supporting 4 GUI frameworks Available at: https://guierrordetector.googlecode.com/ An evaluation on 9 subjects shows its usefulness 36

Recently Viewed Presentations

  • Welcome to AVID Parent/Student Night!

    Welcome to AVID Parent/Student Night!

    Arial Wingdings Times New Roman Tempus Sans ITC Georgia Franklin Gothic Medium Echo 1_Echo Microsoft Excel Chart MVUSD AVID Parent/Student Night! What is AVID? What are the benefits of AVID? How will the AVID program contribute to the success of...
  • National Overdose Deaths Number of Deaths from Prescription

    National Overdose Deaths Number of Deaths from Prescription

    National Overdose Deaths—Number of Deaths from Cocaine. The figure above is a bar chart showing the total number of US overdose deaths involving cocaine from 2001 to 2013. The chart is overlayed by a line graph showing the number of...
  • Ajax - جامعة الملك سعود

    Ajax - جامعة الملك سعود

    The Ajax Control Toolkit contains more than 40 controls, including theAutoComplete, CollapsiblePanel, ColorPicker,MaskedEdit, Calendar, Accordion,HTML Editor Extender, and Watermark controls. Using the Ajax Control Toolkit, you can build Ajax-enabled ASP.NET Web Forms applications by dragging-and-dropping Toolkit controls from the Visual...
  • Kingdom Protista If you look at a drop

    Kingdom Protista If you look at a drop

    A Volvox is a hollow boll composed of hundreds of flagellated cells in a single layer. Chlamydomonas are actually unicellular and flagellated. Fungus-like protists, Myxomycota and Oomycota are decomposers. Phylum Myxomycota are made up of plasmodial slime molds.
  • Available Data and Existing Statistics - SFU.ca

    Available Data and Existing Statistics - SFU.ca

    83) & Ch. 16 (pp.333-41) Quantitative vs. Qualitative Objective Subjective Variables Processes and events Reliability Authenticity Value-Free Explicitly Stated Values Independent of Context Aware of Content Many cases or subjects Few cases or subjects Statistical Analysis Other qualities Detached Researcher...
  • Biomechanics

    Biomechanics

    Anxiety - the negative aspect of experiencing stress. State anxiety - anxiety felt in a specific situation. Trait anxiety - general levels of anxiety for a person in any situation. Somatic anxiety - the feelings of anxiety associated with the...
  • Penguin Predation and Competition Jean Pennycook www.penguinscience.com The

    Penguin Predation and Competition Jean Pennycook www.penguinscience.com The

    Weddell seals do not eat penguins, but they do eat the same food that penguins do: Antarctic silver fish. For the time being there is enough for everyone, but as commercial fishing starts to deplete the Southern Ocean of fish,...
  • Hamlet Resource Pack Aim: to evaluate the technical

    Hamlet Resource Pack Aim: to evaluate the technical

    Dramatic devices. Adaptations. Analysis of quotations. Essay writing technique. The God of Small Things Resource Pack. Aim: to evaluate the technical and conceptual elements of the novel, in depth, with perceptive insight and interpretation.