Search

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.

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.

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.

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.

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 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.