WODA+PERTEA 2014: Joint 12th International Workshop on Dynamic Analysis (WODA) and Workshop on Software and System Performance Testing, Debugging, and Analytics (PERTEA)

Accepted Paper
Tue, Jul 22, 13:20 - 13:40, University Room

Intent Fuzzer: Crafting Intents of Death
Raimondas Sasnauskas and John Regehr
(University of Utah, USA)
We present a fuzzing framework for Intents: the core IPC mechanism for intra- and inter-app communication in Android. Since intents lie at a trust boundary between apps, their correctness is important and thorough testing is warranted. The key challenge is to balance the tension between generating intents that applications expect, permitting deep penetration into application logic, and generating intents that trigger interesting bugs that have not been previously uncovered. Our work strikes this balance using a novel combination of static analysis and random test-case generation. Our intent fuzzer crashed dozens of Google core and top Google Play apps, resulting in app restarts or even in a complete OS reboot.

@InProceedings{WODA+PERTEA14p1, author = {Raimondas Sasnauskas and John Regehr}, title = {Intent Fuzzer: Crafting Intents of Death}, booktitle = {Proc.\ WODA+PERTEA}, publisher = {ACM}, pages = {1--5}, doi = {}, year = {2014}, }

Invited Talks 1
Tue, Jul 22, 08:50 - 09:30, University Room

P: A Domain-Specific Language for Asynchronous Event-Driven Programming (Invited Talk Abstract)
Shaz Qadeer
(Microsoft Research, USA)
Asynchrony is fundamental to a broad class of software systems such as device drivers, cloud infrastructure, interacting web services, and client-server web applications. These software systems exhibit reactive and concurrent execution whose control requires carefully designed and implemented protocols. Traditional programming languages provide little support to specify and validate protocols. To address this gap, we have developed a domain-specific language called P for specification, implementation, and validation of protocols in asynchronous software. P is being used inside Microsoft in Windows and Windows Phone for developing device drivers; the USB device driver stack that ships with Windows and Windows Phone is implemented in P. In this talk, I will present the design and implementation of the language features and the systematic testing framework of P. I will also touch upon our current work extending P for programming fault-tolerant distributed services.

@InProceedings{WODA+PERTEA14p6, author = {Shaz Qadeer}, title = {P: A Domain-Specific Language for Asynchronous Event-Driven Programming (Invited Talk Abstract)}, booktitle = {Proc.\ WODA+PERTEA}, publisher = {ACM}, pages = {6--6}, doi = {}, year = {2014}, }

Usable Program Analysis at Google-Scale (Invited Talk Abstract)
Caitlin Sadowski
(Google, USA)
Scalability and usability problems have hindered many attempts at integrating program analysis tools into the developer workflow at Google. This talk introduces the program analysis landscape at Google, and how we have overcome those problems. I will discuss Google's unique software development environment, and how program analysis fits into that environment, including a variety of AST-matching-based compiler analyses for Java and C++ based on the error-prone and clang-tidy open-source projects.

@InProceedings{WODA+PERTEA14p7, author = {Caitlin Sadowski}, title = {Usable Program Analysis at Google-Scale (Invited Talk Abstract)}, booktitle = {Proc.\ WODA+PERTEA}, publisher = {ACM}, pages = {7--7}, doi = {}, year = {2014}, }

Invited Talks 2
Tue, Jul 22, 10:40 - 12:00, University Room

Automated Test Generation for API Proxy Code (Invited Talk Abstract)
Qing Xie
(Accenture, USA)
As part of exposing APIs, API Management tools apply policy workflows to implement various functionalities such as security, caching, traffic management, and analytics. A policy workflow is a set of conditionals where testing involves executing various paths in the workflow. As a workflow becomes more complex, manual writing of tests to cover various paths in the workflow can be laborious, time-consuming, and error prone. To address the preceding problem, we propose a framework for automated test generation to cover various paths in the policy workflow. The generated tests can be used to find faults in the policy workflow implementations. In addition, the generated tests can serve as regression tests to guard against the changes made to a back-end service or to policy workflow.

@InProceedings{WODA+PERTEA14p8, author = {Qing Xie}, title = {Automated Test Generation for API Proxy Code (Invited Talk Abstract)}, booktitle = {Proc.\ WODA+PERTEA}, publisher = {ACM}, pages = {8--8}, doi = {}, year = {2014}, }

Effective Race Detection for Event-Driven Programs (Invited Talk Abstract)
Manu Sridharan
(Samsung Research, USA)
Like shared-memory multi-threaded programs, event-driven programs are susceptible to non-deterministic errors that are hard to reproduce and debug. Mobile application platforms and the web require writing event-driven code, motivating the need for better tools to detect these types of errors. In the first part of this talk, we will show how techniques from data race detection for multi-threaded programs can be applied to detect these bugs, by defining an appropriate notion of a happens-before relation and memory accesses for the underlying platform. While extant data race detectors can be applied to event-driven programs based on the above, the pervasive use of ad hoc synchronization in such programs can lead a race detector to report too many false positives. Race detection for such programs also faces a scalability challenge, as a large number of short-running event handlers can overwhelm standard vector-clock-based techniques. We present a novel race detector EventRacer that addresses both of these challenges. We introduce race coverage, a systematic method for exposing ad hoc synchronization and other key races to the user, significantly reducing false positives. We also present an efficient connectivity algorithm that uses chain decomposition to dramatically decrease the overhead of vector clocks. We show that for client-side web applications, our techniques lead to large performance and precision improvements over state-of-the-art techniques.

@InProceedings{WODA+PERTEA14p9, author = {Manu Sridharan}, title = {Effective Race Detection for Event-Driven Programs (Invited Talk Abstract)}, booktitle = {Proc.\ WODA+PERTEA}, publisher = {ACM}, pages = {9--9}, doi = {}, year = {2014}, }

Invited Talks 3
Tue, Jul 22, 13:40 - 15:00, University Room

On the Probabilistic Analysis of Software (Invited Talk Abstract)
Corina S. Păsăreanu
(NASA Ames Research Center, USA)
Probabilistic software analysis aims at quantifying how likely a target event is to occur, given a probabilistic characterization of the behavior of a program or of its execution environment. Examples of target events may include an uncaught exception, the invocation of a certain method, or the access to confidential information.We are working on a symbolic execution approach to probabilistic software analysis that first computes the conditions to reach the target event, and then tries to quantify the fraction of the input domain satisfying these conditions. Unlike past approaches, that were mostly performed at model level, and were thus only applicable to early software design stages or required explicit (and hard to maintain) abstraction from the code, our techniques are performed directly at the code level. Our techniques are built on top of the Symbolic PathFinder symbolic execution tool. We discuss applications to the analysis of Unmanned Aerial Systems developed at NASA Ames.

@InProceedings{WODA+PERTEA14p10, author = {Corina S. Păsăreanu}, title = {On the Probabilistic Analysis of Software (Invited Talk Abstract)}, booktitle = {Proc.\ WODA+PERTEA}, publisher = {ACM}, pages = {10--10}, doi = {}, year = {2014}, }

Context-Sensitive Delta Inference for Identifying Workload-Dependent Performance Bottlenecks (Invited Talk Abstract)
Xusheng Xiao
(NEC Labs, USA)
Software hangs can be caused by expensive operations in responsive actions (such as time-consuming operations in UI threads). Some of the expensive operations depend on the input workloads, referred to as workload-dependent performance bottlenecks (WDPBs). WDPBs are usually caused by workload-dependent loops (i.e., WDPB loops) that contain relatively expensive operations. Traditional performance testing and single-execution profiling may not reveal WDPBs due to incorrect assumptions of workloads. To address these issues, we propose the Infer approach that predicts WDPB loops under large workloads via inferring iteration counts of WDPB loops using complexity models for the workload size. Infer incorporates a novel concept named context-sensitive delta inference that consists of two parts: temporal inference for inferring the complexity models of different program locations, and spatial inference for identifying WDPB loops as WDPB candidates. We conducted evaluations on two popular open-source GUI applications, and identified impactful WDPBs that caused 10 performance bugs.

@InProceedings{WODA+PERTEA14p11, author = {Xusheng Xiao}, title = {Context-Sensitive Delta Inference for Identifying Workload-Dependent Performance Bottlenecks (Invited Talk Abstract)}, booktitle = {Proc.\ WODA+PERTEA}, publisher = {ACM}, pages = {11--11}, doi = {}, year = {2014}, }

Invited Talks 4
Tue, Jul 22, 15:40 - 17:40, University Room

Detecting and Repairing Performance Bugs using Execution and Code Patterns (Invited Talk Abstract)
Adrian Nistor
(Chapman University, USA)
Software performance is critical for the overall success of a software project. Performance bugs are programming mistakes that slow down program execution. Performance bugs create poor user experience and affect the user-perceived software quality. Even expert programmers can introduce performance bugs, which have already caused serious and highly publicized incidents. Well tested commercial products such as Windows Explorer and Acrobat Reader are also affected by performance bugs. In this talk, we will discuss Toddler, SunCat, and Caramel, three novel techniques for automatically detecting and repairing performance bugs. Unlike profilers, which focus on methods that take a long time to execute, Toddler, SunCat, and Caramel focus on code and execution patterns that are indicative of common programming mistakes affecting performance. The additional information provided by these patterns enable Toddler, SunCat, and Caramel to have better results more automation, fewer false negatives, fewer false positives, automated repair—than profilers for the bugs Toddler, SunCat, and Caramel are designed to find. Toddler, SunCat, and Caramel employ novel dynamic and static analyses. Toddler, SunCat, and Caramel found over 150 previously unknown performance bugs in widely used Java, C/C++, and C# applications, including in mobile applications. Over 100 of these bugs have already been fixed by developers.

@InProceedings{WODA+PERTEA14p12, author = {Adrian Nistor}, title = {Detecting and Repairing Performance Bugs using Execution and Code Patterns (Invited Talk Abstract)}, booktitle = {Proc.\ WODA+PERTEA}, publisher = {ACM}, pages = {12--12}, doi = {}, year = {2014}, }

Language, Compiler, and Runtime System Support towards Highly Scalable Big Data Application (Invited Talk Abstract)
Guoqing Xu
(University of California at Irvine, USA)
Modern computing has entered the era of Big Data. Analyzing data from Twitter, Google, Facebook, Wikipedia, or the Human Genome Project requires the development of scalable platforms that can quickly extract useful information from an ocean of records collected from customers, clinical trial participants, program execution logs, or the Internet. Most of the existing Big Data applications, including Hadoop, Giraph, Hive, Pig, Mahout, or Hyracks are written managed, object-oriented languages such as Java. While the use of such languages simplifies development tasks, the (memory and execution) inefficiencies inherent in these languages can have large impact on the application performance and scalability. When object-orientation meets Big Data, performance problems are significantly magnified, making data-intensive computing systems fail to scale to large datasets. I will talk about several projects we are currently working on to scale Big Data applications by reducing the cost of a managed runtime. Particularly, I will talk about Facade, a compiler and runtime system we have developed to transform a Big Data application into an almost object-bounded application which has been shown to be much more efficient and scale to much larger datasets. I will also briefly mention two other projects, one attempting to provide a memory-oblivious programming model for developers to allow them to write a program without worrying about how to create threads and use memory, and second aiming to trim a big dataset with probabilistic guarantees to facilitate debugging/testing of a Big Data application.

@InProceedings{WODA+PERTEA14p13, author = {Guoqing Xu}, title = {Language, Compiler, and Runtime System Support towards Highly Scalable Big Data Application (Invited Talk Abstract)}, booktitle = {Proc.\ WODA+PERTEA}, publisher = {ACM}, pages = {13--13}, doi = {}, year = {2014}, }

Improving Energy Efficiency of Work-Stealing Parallel Languages (Invited Talk Abstract)
Yu David Liu
(SUNY Binghamton, USA)
At a time when power-hungry data centers and cloud servers become increasingly prevalent, energy efficiency is looming as a first-class design goal for parallel computing. More established solutions to address this challenging problem come from innovations on parallel architectures and operating systems. In this talk, we bring in a new perspective into green parallel computing, improving energy efficiency at the level of programming language runtimes. Our concrete solution is Hermes, a work-stealing language runtime that favorably balances the trade-off between energy and performance. The key insight is that threads in a work-stealing environment -- thieves and victims have varying impacts on the overall program running time, and a coordination of their execution ``tempos'' can lead to energy efficiency with minimal performance loss. The centerpiece of Hermes is two complementary algorithms to coordinate thread tempo: a workpath-sensitive algorithm to determine tempo for each thread based on thief-victim relationships on the execution path, and a workload-sensitive algorithm to select appropriate tempo based on the size of work-stealing deques. On the highest level, Hermes can be viewed as a semantics-aware energy management strategy unifying the language runtime and the hardware, with the language runtime offering clues for judicious tempo settings, and the hardware physically enabling tempo adjustment through standard Dynamic Voltage and Frequency Scaling (DVFS). Hermes is a joint work with Ph.D. student Haris Ribic.

@InProceedings{WODA+PERTEA14p14, author = {Yu David Liu}, title = {Improving Energy Efficiency of Work-Stealing Parallel Languages (Invited Talk Abstract)}, booktitle = {Proc.\ WODA+PERTEA}, publisher = {ACM}, pages = {14--14}, doi = {}, year = {2014}, }

proc time: 0.77