Search

With the rise of the mobile computing market, Android has received tremendous attention from both academia and industry. Application programming in Android is known to have unique characteristics, and Android apps be particularly vulnerable to various security attacks. In response, numerous solutions for particular security issues have been proposed. However, there is little broad understanding about Android app code structure and behaviors along with their implications for app analysis and security defense, especially in an evolutionary perspective. To mitigate this gap, we present a longitudinal characterization study of Android apps to systematically investigate how they are built and execute over time. Through lightweight static analysis and method-level tracing, we examined the code and execution of 17,664 apps sampled from the apps developed in each of eight past years, with respect to metrics in three complementary dimensions. Our study revealed that (1) apps functionalities heavily rely on the Android framework/SDK, and the reliance continues to grow, (2) Activity components constantly dominated over other types of components and were responsible for the invocation of most lifecycle callbacks, (3) event-handling callbacks consistently focused more on user-interface events than system events, (4) the overall use of callbacks has been slowly diminishing over time, (5) the majority of exercised inter-component communications (ICCs) did not carry any data payloads, and (6) sensitive data sources and sinks targeted only one/two dominant categories of information or operations, and the ranking of source/sink categories remained quite stable throughout the eight years. We discuss the implications of our empirical findings for cost-effective app analysis and security defense for Android, and make cost-effectiveness improvement recommendations accordingly.

Malware collusion is a technique utilized by attackers to evade standard detection. It is a new threat where two or more applications, appearing benign, communicate to perform a malicious task. Most proposed approaches aim at detecting stand-alone malicious applications. We point out the need for analyzing data flows across multiple Android apps, a problem referred to as end-to-end flow analysis . In this work, we present a flow analysis for app pairs that computes the risk level associated with their potential communications. Our approach statically analyzes the sensitivity and context of each inter-app flow based on inter-component communication (ICC) between communicating apps, and defines fine-grained security policies for inter-app ICC risk classification. We perform an empirical study on 7,251 apps from the Google Play store to identify the apps that communicate with each other via ICC channels. Our results report four times fewer warnings on our dataset of 197 real app pairs communicating via explicit external ICCs than the state-of-the-art permission-based collusion detection.

During repackaging, malware writers statically inject malcode and modify the control flow to ensure its execution. Repackaged malware is difficult to detect by existing classification techniques, partly because of their behavioral similarities to benign apps. By exploring the app's internal different behaviors, we propose a new Android repackaged malware detection technique based on code heterogeneity analysis . Our solution strategically partitions the code structure of an app into multiple dependence-based regions (subsets of the code). Each region is independently classified on its behavioral features. We point out the security challenges and design choices for partitioning code structures at the class and method level graphs, and present a solution based on multiple dependence relations. We have performed experimental evaluation with over 7,542 Android apps. For repackaged malware, our partition-based detection reduces false negatives (i.e., missed detection) by 30-fold, when compared to the non-partition-based approach. Overall, our approach achieves a false negative rate of 0.35 percent and a false positive rate of 2.97 percent.

Most existing Android malware detection and categorization techniques are static approaches, which suffer from evasion attacks, such as obfuscation. By analyzing program behaviors, dynamic approaches are potentially more resilient against these attacks. Yet existing dynamic approaches mostly rely on characterizing system calls which are subject to system-call obfuscation. This paper presents DroidCat, a novel dynamic app classification technique, to complement existing approaches. By using a diverse set of dynamic features based on method calls and inter-component communication (ICC) Intents without involving permission, app resources, or system calls while fully handling reflection, DroidCat achieves superior robustness than static approaches as well as dynamic approaches relying on system calls. The features were distilled from a behavioral characterization study of benign versus malicious apps. Through three complementary evaluation studies with 34 343 apps from various sources and spanning the past nine years, we demonstrated the stability of DroidCat in achieving high classification performance and superior accuracy compared with the two state-of-the-art peer techniques that represent both static and dynamic approaches. Overall, DroidCat achieved 97% F1-measure accuracy consistently for classifying apps evolving over the nine years, detecting or categorizing malware, 16%–27% higher than any of the two baselines compared. Furthermore, our experiments with obfuscated benchmarks confirmed higher robustness of DroidCat over these baseline techniques. We also investigated the effects of various design decisions on DroidCat’s effectiveness and the most important features for our dynamic classification. We found that features capturing app execution structure such as the distribution of method calls over user code and libraries are much more important than typical security features such as sensitive flows.

To facilitate clone maintenance, various automated tools were proposed to detect code clones by identifying similar token sequences or similar program syntactic structures in source code. They achieved different trade-offs between precision and recall. Inspired by prior work, we developed a new approach CCLearner, a solely token-based clone detection approach using deep learning. Given known clone pairs and non-clone pairs, CCLearner extracts features from each code pair and leverages the features to train a classifier. The classifier is then used to compare methods pair-by-pair in a given codebase to detect clones. We evaluated CCLearner by reusing an existing benchmark of real clone code—BigCloneBench. We split the benchmark such that some data was used for classifier training, and some data was used for testing. With the testing data, we evaluated CCLearner’s effectiveness of clone detection, and also assessed three existing popular clone detection tools: SourcererCC, NiCad, and Deckard. CCLearner outperformed existing tools by achieving a better trade-off between precision and recall. To further investigate whether other machine learning algorithms can perform comparatively as deep learning, we replaced deep learning with five alternative machine learning algorithms in CCLearner, and observed that CCLearner worked best when using deep learning.

There have been extensive investigations on identifying sensitive data flows in Android apps for detecting malicious behaviors. Typical real world apps have a large number of sensitive flows and sinks. Thus, security analysts need to prioritize these flows and data sinks according to their risks, i.e., flow ranking and sink ranking. In this paper, we present an efficient graph-algorithm based risk metric for prioritizing risky flows and sinks in Android grayware apps. The new risk metric is quantitative and can differentiate the sensitivities of flows and sinks in an app. In the experiments, our risk prioritization produces orderings that are highly consistent with manual inspection. To enable post-detection security enforcement of sensitive sinks, we also present an automatic rewriting framework that utilizes the above prioritization technique. Our rewriting strategies are more feasible than the state-of-art solutions by supporting flow- and sink-based rewriting. We implement our prototype as ReDroid. ReDroid is designed for security analysts who manage organizational app repositories and customize third-party apps to satisfy organization imposed security requirements. We use ReDroid to rewrite both benchmark apps and real world grayware.

Despite the popularity of JavaScript for client-side web applications, there is a lack of effective software tools supporting JavaScript development and testing. The dynamic characteristics of JavaScript pose software engineering challenges such as program understanding and security. One important feature of JavaScript is that its objects support flexible mechanisms such as property changes at runtime and prototype-based inheritance, making it difficult to reason about object behavior. We have performed an empirical study on real JavaScript applications to understand the dynamic behavior of JavaScript objects. We present metrics to measure behavior of JavaScript objects during execution e.g., operations associated with an object, object size, and property type changes. We also investigated the behavioral patterns of observed objects to understand the coding or user interaction practices in JavaScript software. Copyright © 2015John Wiley & Sons, Ltd.

As mobile computing becomes an integral part of the modern user experience, malicious applications have infiltrated open marketplaces for mobile platforms. Malware apps stealthily launch operations to retrieve sensitive user or device data or abuse system resources. We describe a highly accurate classification approach for detecting malicious Android apps. Our method statically extracts a data-flow feature on how user inputs trigger sensitive API invocations, a property referred to as the user-trigger dependence. Our evaluation with 1433 malware apps and 2684 free popular apps gives a classification accuracy (2.1% false negative rate and 2.0% false positive rate) that is better than, or at least competitive against, the state-of-the-art. Our method also discovers new malicious apps in the Google Play market that cannot be detected by virus scanning tools. Our thesis in this mobile app classification work is to advocate the approach of benign property enforcement, i.e., extracting unique behavioral properties from benign programs and designing corresponding classification policies.

Security transformation is to transfer applications to meet security guarantees. How to prioritize Android apps and find suitable transformation options is a challenging problem. Typical real-world apps have a large number of sensitive flows and sinks. Thus, security analysts need to prioritize these flows and data sinks according to their risks, i.e., flow ranking and sink ranking. We present an efficient graph-algorithm based risk metric for prioritizing risky flows and sinks in Android grayware apps. Our risk prioritization produces orderings that are consistent with published security reports. We demonstrate a new automatic app transformation framework that utilizes the above prioritization technique to improve app security. The framework provides more rewriting options than the state-of-art solutions by supporting flow-and sink-based security checks. Our prototype ReDroid is designed for security analysts who manage organizational app repositories and customize third-party apps to satisfy organization imposed security requirements. Our framework enables application transformation for both benchmark apps and real-world grayware to strengthen their security guarantees.

We describe a set of artifacts for dynamic analysis of Android apps, including a dataset used in a dynamic characterization study, source code used for performing the study, an Android inter-app benchmark suite, and definition of Android behavioral metrics.

Most existing research for Android focuses on particular security issues, yet there is little broad understanding of Android application run-time characteristics and their implications. To mitigate this gap, we present the first systematic dynamic characterization study of Android apps that targets a broad understanding of application behaviors in Android. Through lightweight method-level profiling, we collected 59GB traces of method calls and Intent-based inter-component communication (ICC) from 125 popular Android apps and 62 pairs among them that enabled an intensive empirical investigation of their run-time behaviors. Our study revealed that, among other findings, (1) the application executions were overwhelmingly dominated by the Android framework, (2) Activity components dominated over other types of components and were responsible for most lifecycle callbacks (3) most event handlers dealt with user interactions as opposed to system events, (4) the majority of exercised ICCs did not carry any data payloads, and (5) sensitive data sources and sinks targeted only one/two dominant categories of information or operations. We also discuss the implications of our results for cost-effective program analysis and security defense for Android.

Programmers produce code clones when developing software. By copying and pasting code with or without modification, developers reuse existing code to improve programming productivity. However, code clones present challenges to software maintenance: they may require consistent application of the same or similar bug fixes or program changes to multiple code locations. To simplify the maintenance process, various tools have been proposed to automatically detect clones [1], [2], [3], [4], [5], [6]. Some tools tokenize source code, and then compare the sequence or frequency of tokens to reveal clones [1], [3], [4], [5]. Some other tools detect clones using tree-matching algorithms to compare the Abstract Syntax Trees (ASTs) of source code [2], [6]. In this paper, we present CCLEARNER, the first solely token-based clone detection approach leveraging deep learning. CCLEARNER extracts tokens from known method-level code clones and nonclones to train a classifier, and then uses the classifier to detect clones in a given codebase.To evaluate CCLEARNER, we reused BigCloneBench [7], an existing large benchmark of real clones. We used part of the benchmark for training and the other part for testing, and observed that CCLEARNER effectively detected clones. With the same data set, we conducted the first systematic comparison experiment between CCLEARNER and three popular clone detection tools. Compared with the approaches not using deep learning, CCLEARNER achieved competitive clone detection effectiveness with low time cost.

As the Android app market keeps growing, there is a pressing need for automated tool supports to empower Android developers to produce quality apps with higher productivity. Yet existing tools for Android mostly aim at security and privacy protection, primarily targeting end users and security analysts. Towards filling this gap, we present DROIDFAX, a toolkit that targets the developers to help them comprehensively understand Android apps regarding their code structure and behavioral traits. To that end, DROIDFAX features a systematic app characterization in multiple dimensions and views, through lightweight code analysis and profiling of both ordinary method calls (including those via reflection and exceptional control flows) and inter-component communications (including those within and across apps). The toolkit also includes a statement coverage tracker that works directly on bytecode and a dedicated tracer of events occurred during app executions. Applying DROIDFAX in two use cases has resulted in important findings about app behavioral patterns and an advanced security defense technique for Android. Empirical results also showed promising efficiency and scalability of DROIDFAX for practical adoption. A demo video for DROIDFAX can be viewed here or downloaded here.

Inter-Component Communication (ICC) enables useful interactions between mobile apps. However, misuse of ICC exposes users to serious threats, allowing malicious apps to access privileged user data via another app. Unfortunately, existing ICC analyses are largely insufficient in both accuracy and scalability. Most approaches rely on single-app ICC analysis which results in inaccurate and excessive alerts. A few recent works use pairwise app analysis, but are limited by small data sizes and scalability. In this paper, we present MR-Droid, a MapReduce-based computing framework for accurate and scalable inter-app ICC analysis in Android. MR-Droid extracts data-flow features between multiple communicating apps to build a large-scale ICC graph. We leverage the ICC graph to provide contexts for inter-app communications to produce precise alerts and prioritize risk assessments. This scheme requires quickly processing a large number of app-pairs, which is enabled by our MapReduce-based program analysis. Extensive experiments on 11,996 apps from 24 app categories (13 million pairs) demonstrate the effectiveness of our risk prioritization scheme. Our analyses also reveal new real-world hijacking attacks and collusive app pairs. Based on our findings, we provide practical recommendations for reducing inter-app communication risks.

Inter-Component Communication (ICC) enables useful interactions between mobile apps. However, misuse of ICC exposes users to serious threats such as intent hijacking/spoofing and app collusions, allowing malicious apps to access privileged user data via another app. Unfortunately, existing ICC analyses are largely incompetent in both accuracy and scale. This poster points out the need and technical challenges of prioritized analysis of inter-app ICC risks. In this poster, we propose MR-Droid, a MapReduce-based computing framework for accurate and scalable inter-app ICC analysis in Android. MR-Droid extracts data-flow features between multiple communicating apps and the target apps to build a large-scale ICC graph. Our approach is to leverage the ICC graph to provide contexts for inter-app communications to produce precise alerts and prioritize risk assessments. This process requires large app-pair data, which is enabled by our MapReduce-based program analysis. Our initial extensive experiments on 11,996 apps from 24 app categories (13 million pairs) demonstrate the scalability of our approach.

Static analysis is challenged by the dynamic language constructs of JavaScript which often lead to unacceptable performance and/or precision results. We describe an approach that focuses on improving the practicality and accuracy of points-to analysis and call graph construction for JavaScript programs. The approach first identifies program constructs which are sources of imprecision (i.e., root causes) through monitoring the static analysis process. We then examine and suggest specific context-sensitive analyses to apply. Our technique is able to to find that the root causes comprise less than 2% of the functions in JavaScript library applications. Moreover, the specialized analysis derived by our approach finishes within a few seconds, even on programs which can not complete within 10 minutes with the original analysis.

Program anomaly detection models legitimate behaviors of complex software and detects deviations during execution. Behavior deviations may be caused by malicious exploits, design flaws, or operational errors. Probabilistic detection computes the likelihood of occurrences of observed call sequences. However, maintaining context sensitivity in detection incurs high modeling complexity and runtime overhead. We present a new anomaly-based detection technique that is both probabilistic and 1-level calling-context sensitive. We describe a matrix representation and clustering-based solution for model reduction, specifically reducing the number of hidden states in a special hidden Markov model whose parameters are initialized with program analysis. Our extensive experimental evaluation confirms the significantly improved detection accuracy and shows that attacker's ability to conduct code-reuse exploits is substantially limited.

There is tension between programming language design for modularity and flexibility of programming and the amenability of the resulting programs to static analysis. At the start of Software Practice and Experience in 1971, most languages in commercial use were procedural (e.g., FORTRAN, ALGOL, PL/I) and on the whole were easier to analyze than languages of today such as JavaScript and Python. Modern languages include dynamic features, which enhance prototyping of approaches, often resulting in programs that are difficult for software tools or humans to understand. Starting with this perspective, we explore the relationship between language features and the ability of static analysis to precisely determine control flow and data flow in programs, thus enabling program optimization, transformation and understanding.

Call graphs are widely used to represent calling relationships among methods. However, there is not much interest in calling relationships among library methods in many software engineering applications, such as program understanding and testing, especially when the library is very big and the calling relationships are not trivial. This paper explores approaches for generating more accurate application call graphs for Java. A new data reachability algorithm is proposed and fine tuned to resolve library callbacks accurately. Compared with an algorithm that resolves library callbacks by traversing the whole-program call graph, the fine-tuned data reachability algorithm results in fewer spurious callback edges. In empirical studies, the new algorithm shows a significant reduction in the number of spurious callback edges. On the basis of the new algorithm, a library abstraction can be calculated automatically and applied in amortized slicing and dataflow testing. Copyright © 2007 John Wiley & Sons, Ltd.

The trend constantly being observed in the evolution of advanced modern exploits is their growing sophistication in stealthy attacks. Code-reuse attacks such as return-oriented programming allow intruders to execute mal-intended instruction sequences on a victim machine without injecting external code. We introduce a new anomaly-based detection technique that probabilistically models and learns a program's control flows for high-precision behavioral reasoning and monitoring. Our prototype in Linux is named STILO, which stands for STatically InitiaLized markOv. Experimental evaluation involves real-world code-reuse exploits and over 4,000 testcases from server and utility programs. STILO achieves up to 28-fold of improvement in detection accuracy over the state-of-the-art HMM-based anomaly detection. Our findings suggest that the probabilistic modeling of program dependences provides a significant source of behavior information for building high-precision models for real-time system monitoring.

During program maintenance, a programmer may make changes that enhance program functionality or fix bugs in code. Then, the programmer usually will run unit/regression tests to prevent invalidation of previously tested functionality. If a test fails unexpectedly, the programmer needs to explore the edit to find the failure-inducing changes for that test. Crisp uses results from Chianti, a tool that performs semantic change impact analysis, to allow the programmer to examine those parts of the edit that affect the failing test. Crisp then builds a compilable intermediate version of the program by adding a programmer-selected partial edit to the original code, augmenting the selection as necessary to ensure compilation. The programmer can reexecute the test on the intermediate version in order to locate the exact reasons for the failure by concentrating on the specific changes that were applied. In nine initial case studies on pairs of versions from two real Java programs, Daikon and Eclipse jdt compiler, we were able to use Crisp to identify the failure-inducing changes for all but 1 of 68 failing tests. On average, 33 changes were found to affect each failing test (of the 67), but only 1-4 of these changes were found to be actually failure-inducing

Software engineering research and programming language design have enjoyed a symbiotic relationship, with traceable impacts since the 1970s, when these areas were first distinguished from one another. This report documents this relationship by focusing on several major features of current programming languages: data and procedural abstraction, types, concurrency, exceptions, and visual programming mechanisms. The influences are determined by tracing references in publications in both fields, obtaining oral histories from language designers delineating influences on them, and tracking cotemporal research trends and ideas as demonstrated by workshop topics, special issue publications, and invited talks in the two fields. In some cases there is conclusive data supporting influence. In other cases, there are circumstantial arguments (i.e., cotemporal ideas) that indicate influence. Using this approach, this study provides evidence of the impact of software engineering research on modern programming language design and documents the close relationship between these two fields.

This paper presents a new compile-time analysis that enables a testing methodology for white-box coverage testing of error recovery code (i.e., exception handlers) of server applications written in Java, using compiler-directed fault injection. The analysis allows compiler-generated instrumentation to guide the fault injection and to record the recovery code exercised. (An injected fault is experienced as a Java exception.) The analysis 1) identifies the exception-flow "def-uses" to be tested in this manner, 2) determines the kind of fault to be requested at a program point, and 3) finds appropriate locations for code instrumentation. The analysis incorporates refinements that establish sufficient context sensitivity to ensure relatively precise def-use links and to eliminate some spurious def-uses due to demonstrably infeasible control flow. A runtime test harness calculates test coverage of these links using an exception def-catch metric. Experiments with the methodology demonstrate the utility of the increased precision in obtaining good test coverage on a set of moderately sized server benchmarks.

The goal of points-to analysis for Java is to determine the set of objects pointed to by a reference variable or a reference object field. We present object sensitivity , a new form of context sensitivity for flow-insensitive points-to analysis for Java. The key idea of our approach is to analyze a method separately for each of the object names that represent run-time objects on which this method may be invoked. To ensure flexibility and practicality, we propose a parameterization framework that allows analysis designers to control the tradeoffs between cost and precision in the object-sensitive analysis. Side-effect analysis determines the memory locations that may be modified by the execution of a program statement. Def-use analysis identifies pairs of statements that set the value of a memory location and subsequently use that value. The information computed by such analyses has a wide variety of uses in compilers and software tools. This work proposes new versions of these analyses that are based on object-sensitive points-to analysis.We have implemented two instantiations of our parameterized object-sensitive points-to analysis. On a set of 23 Java programs, our experiments show that these analyses have comparable cost to a context-insensitive points-to analysis for Java which is based on Andersen's analysis for C. Our results also show that object sensitivity significantly improves the precision of side-effect analysis and call graph construction, compared to (1) context-insensitive analysis, and (2) context-sensitive points-to analysis that models context using the invoking call site. These experiments demonstrate that object-sensitive analyses can achieve substantial precision improvement, while at the same time remaining efficient and practical.

The use of pointers presents serious problems for software productivity tools for software understanding, restructuring, and testing. Pointers enable indirect memory accesses through pointer dereferences, as well as indirect procedure calls (e.g., through function pointers in C). Such indirect accesses and calls can be disambiguated with pointer analysis. In this paper we evaluate the precision of one specific pointer analysis (the FA pointer analysis by Zhang et al.) for the purposes of call graph construction for C programs with function pointers. The analysis is incorporated in a production-strength code-browsing tool from Siemens Corporate Research in which the program call graph is used as a primary tool for code understanding. The FA pointer analysis uses an inexpensive, almost-linear, flow- and context-insensitive algorithm. To measure analysis precision, we compare the call graph constructed by this analysis with the most precise call graph obtainable by a large category of existing pointer analyses. Surprisingly, for all our data programs the FA analysis achieves the best possible precision. This result indicates that for the purposes of call graph construction, inexpensive pointer analyses may provide precision comparable to the precision of expensive pointer analyses.

There has long been a close association between research in software engineering and the design of programming languages. Part of the IMPACT project involves an exploration of the interrelations of these two fields and documentation in a report of how fundamental research in software engineering has been a valuable resource for programming language features commonly used today. The resulting report investigates the relationship by considering features in currently used languages, including exceptions, control and data abstractions, types, inheritance, concurrency and visualization mechanisms.This paper, exerpted from the report, focuses on the influence of software engineering research on the development of exceptions. The paper demonstrates that there is a symbiotic relationship between software engineering research and the design of exception handing in programming languages. Publication of these partial results is aimed at soliciting feedback and comments from both the programming languages and software engineering communities.

Program anomaly detection analyzes normal program behaviors and discovers aberrant executions caused by attacks, misconfigurations, program bugs, and unusual usage patterns. The merit of program anomaly detection is its independence from attack signatures, which enables proactive defense against new and unknown attacks. In this paper, we formalize the general program anomaly detection problem and point out two of its key properties. We present a unified framework to present any program anomaly detection method in terms of its detection capability. We prove the theoretical accuracy limit for program anomaly detection with an abstract detection machine. We show how existing solutions are positioned in our framework and illustrate the gap between state-of-the-art methods and the theoretical accuracy limit. We also point out some potential modeling features for future program anomaly detection evolution.

The goal of points-to analysis for Java is to determine the set of objects pointed to by a reference variable or a reference objet field. Improving the precision of practical points-to analysis is important because points-to information has a wide variety of client applications in optimizing compilers and software engineering tools. In this paper we present object sensitivity, a new form of context sensitivity for flow-insensitive points-to analysis for Java. The key idea of our approach is to analyze a method separately for each of the objects on which this method is invoked. To ensure flexibility and practicality, we propose a parameterization framework that allows analysis designers to control the tradeoffs between cost and precision in the object-sensitive analysis. Side-effect analysis determines the memory locations that may be modified by the execution of a program statement. This information is needed for various compiler optimizations and software engineering tools. We present a new form of side-effect analysis for Java which is based on object-sensitive points-to analysis.We have implemented one instantiation of our parameterized object-sensitive points-to analysis. We compare this instantiation with a context-insensitive points-to analysis for Java which is based on Andersen's analysis for C [4]. On a set of 23 Java programs, our experiments show that the two analyses have comparable cost. In some cases the object-sensitive analysis is actually faster than the context-insensitive analysis. Our results also show that object sensitivity significantly improves the precision of side-effect analysis, call graph construction, and virtual call resolution. These experiments demonstrate that object-sensitive analyses can achieve significantly better precision than context-insensitive ones, while at the same time remaining efficient and practical.

At each program point, points-to analysis for statically typed object oriented programming languages (e.g., Java, C++) determines those objects to which a reference may refer (or a pointer may point) during execution. Points-to analysis is necessary for any semantics based software tools for object oriented systems. Our new complexity results for points-to analysis distinguish the difficulty of intraprocedural and interprocedural points-to analyses for languages with combinations of single-level types (i.e., types with data members only of primitive type), exceptions with or without subtyping, and dynamic dispatch. Our results include: 1) the first polynomial-time algorithm for points-to analysis in the presence of exceptions that handles a robust subset of Java without threads and can be applied to C++; 2) proof that the above algorithm is safe, in general, and provably precise on programs with single-level types and exceptions without subtyping, but not dynamic dispatch, thus, this case is in P; 3) proof that an interprocedural points-to analysis problem with single-level types and exceptions with subtyping, but without dynamic dispatch, is PSPACE-hard, while the intraprocedural problem is PSPACE-complete. Other complexity characterizations of points-to analysis in programs without exceptions are presented, including an algorithm with worst-case bound of O(n/sup 5/), which improves over the O(n/sup 7/) worst-case bound achievable from previous approaches of T. Reps et al. (1995) and W.A. Landi and B.G. Ryder (1991).

The frequent occurrence of implicitly thrown exceptions poses one of the challenges present in a Java compiler. Not only do these implicitly thrown exceptions directly affect the performance by requiring explicit checks, they also indirectly impact the performance by restricting code movement in order to satisfy the precise exception model in Java. In particular, instruction scheduling is one transformation that is restricted by implicitly thrown exceptions due to the heavy reliance on reordering instructions to exploit maximum hardware performance. The goal of this study is two-fold: first, investigate the degree to which implicitly thrown exceptions in Java hinder instruction scheduling, and second, find new techniques for allowing more efficient execution of Java programs containing implicitly thrown exceptions. Experimental results show that with aggressive scheduling techniques, such as superblock scheduling, the negative performance impact can be greatly reduced.

Precision and scalability are two desirable, yet often conflicting, features of data-flow analyses. This paper reports on a case study of the modification---ide-effects problem for C in the presence of pointers from the perspective of contrasting the flow and context sensitivity of the solution procedure with respect to precision and scalability. The results show that the cost of precision of flow- and context-sensitive analysis is not always prohibitive, and that the precision of flow- and context-insensitive analysis is substantially better than worst-case estimates and can be sufficient for certain applications. Program characteristics that affect the performance of data-flow analysis are identified.

JavaScript is widely used in Web applications because of its flexibility and dynamic characteristics. However, the latter (e.g., runtime code generation and dynamic object behavior) pose challenges for program understanding, security, etc. We have designed the JavaScript Blended Analysis Framework, a program analysis framework that combines dynamic and static analyses. JSBAF expands the capability of static analysis for the dynamically generated code and variadic functions. We also present a novel context-sensitive points-to analysis that more precisely models JavaScript objects. Empirical results on popular JavaScript websites show that our analyses are substantially more accurate than existing approaches.

JavaScript object behavior is dynamic and adheres to prototype-based inheritance. The behavior of a JavaScript object can be changed by adding and removing properties at runtime. Points-to analysis calculates the set of values a reference property or variable may have during execution. We present a novel, partially flow-sensitive, context-sensitive points-to algorithm that accurately models dynamic changes in object behavior. The algorithm represents objects by their creation sites and local property names; it tracks property updates via a new control-flow graph representation. The calling context comprises the receiver object, its local properties and prototype chain. We compare the new points-to algorithm with an existing JavaScript points-to algorithm in terms of their respective performance and accuracy on a client application. The experimental results on real JavaScript websites show that the new points-to analysis significantly improves precision, uniquely resolving on average 11% more property lookup statements.

JavaScript is widely used in Web applications because of its flexibility and dynamic features. However, the latter pose challenges to static analyses aimed at finding security vulnerabilities, (e.g., taint analysis). We present blended taint analysis, an instantiation of our general-purpose analysis framework for JavaScript, to illustrate how a combined dynamic/static analysis approach can deal with dynamic features by collecting generated code and other information at runtime. In empirical comparisons with two pure static taint analyses, we show blended taint analysis to be both more scalable and precise on JavaScript benchmark codes extracted from 12 popular websites at alexa. Our results show that blended taint analysis discovered 13 unique violations in 6 of the websites. In contrast, each of the static analyses identified less than half of these violations. Moreover, given a reasonable time budget of 10 minutes, both static analyses encountered webpages they could not analyze, sometimes significantly many such pages. Case studies demonstrate the quality of the blended taint analysis solution in comparison to that of pure static analysis.

We present an effective approach to performing data flow analysis in parallel and identify three types of parallelism inherent in this solution process: independent-problem parallelism, separate-unit parallelism and algorithmic parallelism. We present our investigations of Fortran procedures from thePerfect Benchmarks andnetlib libraries, which reveal structural characteristics of program flow graphs that are amenable to algorithmic parallelism. Previously, the utility of algorithmic parallelism had been explored using our parallel hybrid algorithm in the context of solving the Reaching Definitions problem for Fortran procedures. Here we present new refinements that optimize performance by increasing the grain size of the parallelism, to improve communication on distributed-memory machines. The empirical performance of our optimized and unoptimized hybrid algorithms for Reaching Definitions are compared on this large data set using an iPSC/2. Our empirical findings qualitatively validate the usefulness of algorithmic parallelism.

Def-use analysis links possible value-setting statements for a variable (i.e. definitions) to potential value-fetches (i.e. uses) of that value. This paper describes the first algorithm that calculates accurate interprocedural def-use associations in C software systems. Our algorithm accounts for program-point-specific pointer-induced aliases, though it is currently limited to programs using a single level of indirection. We prove the NP-hardness of the interprocedural reaching definitions problem and describe the approximations made by our polynomial-time algorithm. Initial empirical results are also presented. >

Various coverage criteria are commonly used to assess the quality of test suites, but achieving full coverage according to these criteria is often impossible or impractical. Our research starts from the popular assumption that a disproportionate number of faults is likely to reside in recently changed code. Based on this assumption, we propose several change-based coverage criteria that reflect to what extent changes with respect to a previous program version are exercised by a test suite. In a set of experiments on programs from the SIR repository, we found change-based criteria to reveal faults bet- ter than traditional criteria, and to enable the construction of much smaller test suites with similar fault detection effectiveness. We also report on a case study that shows that achieving 100% coverage according to a change-based criterion is feasible and that by doing so we were able to find additional faults, including one fault that was not intentionally seeded in the subject program.

Non-concurrency analysis is a set of techniques for statically identifying pairs (or sets) of statements in a concurrent program which can never happen together. This information aids programmers in debugging and manually optimizing programs, improves the precision of data flow analysis, enables optimized translation of rendezvous, facilitates dead code elimination and other automatic optimizations, and allows anomaly detection in explicitly parallel programs. We present a framework for non-concurrency analysis, capable of incorporating previous analysis algorithms [CS88, DS92] and improving upon them. We show general theoretical results which are useful in estimating non-concurrency, and examples of non-concurrency analysis frameworks for two synchronization primitives: the Ada rendezvous and binary semaphores. Both of these frameworks have a low-order polynomial bound on worst-case solution time. We provide experimental evidence that static non-concurrency analysis of Ada programs can be accomplished in a reasonable time, and is generally quite accurate. Our framework, and the set of refinement components we develop, also exhibits dramatic accuracy improvements over [DS91], when the latter is used as a stand-alone algorithm, as demonstrated by our experiments.

In prior work we have developed an escape analysis to help developers identify sources of object churn (i.e., excessive use of temporaries) in large framework-based applications. We have developed Hi-C, an Eclipse plug-in that allows users to visualize, filter, and explore analysis results to aid them in diagnosis of object churn and in program comprehension in general.

This paper explores the use of context sensitivity both intra- and interprocedurally in a blended (static/dynamic) program analysis for identifying source of object churn in framework-intensive Web-based applications. Empirical experiments with an existing blended analysis algorithm [10] compare combinations of (i) use of a context-insensitive call graph with a context-sensitive calling context tree, and (ii) use (or not) of context-sensitive code pruning within methods. These experiments demonstrate achievable gains in scalability and performance in terms of several metrics designed for blended escape analysis, and report results in terms of object instances created, to allow more realistic conclusions from the data than were possible previously.

This paper describes the implementation and evaluation of a program that uses active recruiting and peer-led team learning to try to increase the participation and success of women and minority students in undergraduate computer science. These strategies were applied at eight universities starting in the fall of 2004. There have been some impressive results: We succeeded in attracting under-represented students who would not otherwise have taken a CS course. Evaluation shows that participation in our program significantly improves retention rates and grades, especially for women. Students in the program, as well as the students who served as peer leaders, are uniformly enthusiastic about their experience.

In modern software systems, programs are obtained by dynamically assembling components. This has made it necessary to subject component providers to access-control restrictions. What permissions should be granted to each component? Too few permissions may cause run-time authorization failures, too many constitute a security hole. We have designed and implemented a composite algorithm for precise static permission analysis for Java and the CLR. Unlike previous work, the analysis is modular and fully integrated with a novel slicing-based string analysis that is used to statically compute the string values defining a permission and disambiguate permission propagation paths. The results of our research prototype on production-level Java code support the effectiveness, practicality, and precision of our techniques, and show outstanding improvement over previous work.

Framework-intensive applications (e.g., Web applications) heavily use temporary data structures, often resulting in performance bottlenecks. This paper presents an optimized blended escape analysis to approximate object lifetimes and thus, to identify these temporaries and their uses. Empirical results show that this optimized analysis on average prunes 37% of the basic blocks in our benchmarks, and achieves a speedup of up to 29 times compared to the original analysis. Newly defined metrics quantify key properties of temporary data structures and their uses. A detailed empirical evaluation offers the first characterization of temporaries in framework-intensive applications. The results show that temporary data structures can include up to 12 distinct object types and can traverse through as many as 14 method invocations before being captured.

Software development teams exchange source code in shared repositories. These repositories are kept consistent by having developers follow a commit policy, such as “Program edits can be committed only if all available tests succeed.” Such policies may result in long intervals between commits, increasing the likelihood of duplicative development and merge conflicts. Furthermore, commit policies are generally not automatically enforceable. We present a program analysis to identify committable changes that can be released early, without causing failures of existing tests, even in the presence of failing tests in a developer's local workspace. The algorithm can support relaxed commit policies that allow early release of changes, reducing the potential for merge conflicts. In experiments using several versions of a non-trivial software system with failing tests, 3 newly enabled commit policies were shown to allow a significant percentage of changes to be committed.

Incremental data flow analysis algorithms have been designed to deal efficiently with change in evolving software systems. These algorithms document the current state of a software system by incorporating change effects into previously derived information describing the definition and use of data in the system. Unfortunately, the performance of these algorithms cannot, in general, be characterized by analytic predictions of their expected behavior. It is possible, however, to observe their performance empirically and predict their average behavior. The authors report on experiments on the empirical profiling of a general-purpose, incremental data flow analysis algorithm. The algorithm, dominator based and coded in C, was applied to statistically significant numbers of feasible, random software systems of moderate size. The experimental results, with quantifiable confidence limits, substantiate the claim that incremental analyses are viable and grow more valuable as a software system grows in size. >

This paper defines a new analysis paradigm, blended program analysis, that enables practical, effective analysis of large framework-based Java applications for performance understanding. Blended analysis combines a dynamic representation of the program calling structure, with a static analysis applied to a region of that calling structure with observed performance problems. A blended escape analysis is presented which enables approximation of object effective lifetimes, to facilitate explanation of the usage of newly created objects in a program region. Performance bottlenecks stemming from overuse of temporary structures are common in framework-based applications. Metrics are introduced to expose how, in aggregate, these applications make use of new objects. Results of empirical experiments with the Trade benchmark are presented. A case study demonstrates how results from a blended escape analysis can help locate, in a region which calls 223 distinct methods, the single call path responsible for a performance problem involving objects created at 9 distinct sites and as far as 6 call levels away.

Knowledge of interclass test dependences is crucial to decide class test order, facilitating the design of an efficient integration test plan. In order to discover precise interclass test dependences, we proposed a semantic-based definition and designed a safe approximation algorithm to calculate the dependence according to the given definition. The algorithm propagates semantic dependences at method-level granularity and is parameterized by the precision of the corresponding program analysis. We have experimented with nine benchmarks and showed that the algorithm is rather accurate in that it discovers dependence cycles precisely in 6 out of 9 benchmarks (as evaluated by human inspection). The algorithm uncovers additional opportunities for concurrent testing in each of the benchmarks, with an on average expected 52.5% time savings over the ORD-based definition.

Crisp is an Eclipse plug-in tool for constructing intermediate versions of a Java program that is being edited. After a long editing session, a programmer will run regression tests to make sure she has not invalidated previously tested functionality. If a test fails unexpectedly, Crisp allows the programmer to select parts of the edit that affected the failing test and to add them to the original program, creating an intermediate version guaranteed to compile. Then the programmer can re-execute the test in order to locate the exact reasons for the failure by concentrating on those affecting changes that were applied. Using Crisp, a programmer can it- eratively select, apply, and undo individual (or sets of) affecting changes and, thus effectively find a small set of failure-inducing changes. Crisp is an extension to our change impact analysis tool, Chianti, [6].

Although it is common in large Java programs to rethrow exceptions, existing exception-flow analyses find only single exception-flow links, thus are unable to identify multiple-link exception propagation paths. This paper presents a new static analysis that, when combined with previous exception-flow analyses, computes chains of semantically-related exception-flow links, and thus reports entire exception propagation paths, instead of just discrete segments of them. These chains can be used 1) to show the error handling architecture of a system, 2) to assess the vulnerability of a single component and the whole system, 3) to support better testing of error recovery code, and 4) to facilitate the tracing of the root cause of a logged problem. Empirical findings and a case history for Tomcat show that a significant portion of the chains found in our benchmarks span multiple components, and thus are hard to find manually.