Browsing by Author "KHOO, Siau-Cheng"
Now showing 1 - 11 of 11
Results Per Page
Sort Options
- ItemBounded Size-change Termination(2005-08-03T02:49:06Z) KHOO, Siau-Cheng; ANDERSON, HughThe size-change principle devised by Lee, Jones and Ben-Amram, provides an effective method of determining program termination for recursive functions over well-founded types. In this paper, we extend size-change termination beyond the original well-founded condition to include arbitrary bounds that are expressed by linear constraints. Our bounded termination condition determines if repeated calls to a function will monotonically move the call arguments toward the boundary of the guard. We also present a technique which allows the analysis of functions in which there turn values are relevant to termination. Our analysis exploits the decidability and expressive power of affine constraints. These techniques significantly extend the set of programs that are size-change terminating.
- ItemA Comparison between MDPP and Kernel Regression Smoothing Techniques for Forecasting Time Series Data(2005-02-07T02:56:23Z) LUCA, Beatrice; KHOO, Siau-ChengWe present a comparison between two smoothing techniques for forecasting time series, Minimal Distance Percentage Principle (MDPP) and non-parametric Kernel Regression. This comparison reveals some important aspects such as the choice of the smoothing parameters, the complexity of the algorithms and the accuracy of the smoothing results used in forecasting. We have chosen to make tests on the predictive power of "head-and-shoulder" pattern. Financial analysts are overloaded with huge historical stock data which makes searching for chart patterns a difficult job. This is the reason why we need to take smoothing as an integral part of pattern definition, ie., to find, through the smoothing process, those landmarks which are important in the pattern formation. Our final goal is to find as many good instances of "head-and-shoulder" pattern using MDPP and kernel Regression smoothing techniques, and to forecast the future time series prices.
- ItemCOPPICE: Discovering Complete API Rules through Mutation Testing(2012-03-27T09:01:47Z) NGUYEN, Anh Cuong; KHOO, Siau-ChengSpecifications are important for many activities during software construction and maintenance process such as testing, verification, debugging and repairing. Despite their importance, specifications are often missing, informal or incomplete because they are difficult to write manually. Many techniques have been proposed to automatically mine specifications describing method call sequence from execution traces or source code using frequent pattern mining. Unfortunately, a sizeable number of such “interesting” specifications discovered by frequent pattern mining may not capture the correct use patterns of method calls. Consequently, when used in software testing or verification, these mined specifications lead to many false positive defects, which in turn consume much effort for manual investigation. We present a novel framework for automatically discovering legitimate specifications from execution traces using a mutation testing based approach. Such an approach gives a semantics bearing to the legitimacy of the discovered specifications. We introduce the notion of maximal precision and completeness as the desired forms of discovered specifications, and describe in detail suppression techniques that aid efficient discovery. Preliminary evaluation of this approach on several open source software projects shows that specifications discovered through our approach, compared with those discovered through frequent pattern mining, are much more precise and complete. When used in finding bugs, our specifications also locate defects with significantly fewer false positives and more true positives.
- ItemExtracting Significant Specifications from Mining through Mutation Testing (Technical Report)(2011-07-12T01:42:26Z) NGUYEN, Anh Cuong; KHOO, Siau-ChengSpecification mining techniques are used to automatically infer interaction specifications among objects in the format of call sequences, but many of these specifications can be meaningless or insignificant. As a consequence, when used in program testing or formal verification, the presence of these leads to false positive defects, which in turn demand much effort for manual investigation. We propose a novel process for determining and extracting significant specifications from a set of mined specifications using mutation testing. The resulting specifications can then be used with program verification to detect defects with high accuracy. To our knowledge, this is the first fully automatic approach for extracting significant specifications from mining using program testing. We evaluate our approach through mining significant specifications for the Java API and use them to find real defects in many systems.
- ItemIterative Statistical Bug Isolation via Hierarchical Instrumentation(2014-07-14) ZUO, Zhiqiang; KHOO, Siau-ChengCooperative statistical bug isolation approaches monitor program runtime behavior from end-user executions and apply statistical techniques to pinpoint likely causes of eld failures. Having end-users to run fully instrumented programs is extremely undesirable, as it adds tremendous performance overhead to end-users; it is also unnecessary, since in practice major part of these programs are error-free and need no instrumentation. In order to reduce the monitoring and computational costs as well as the performance overhead of end-users, we propose a novel iterative (and cooperative) statistical bug isolation approach for eld failures via hierarchical instrumentation (HI). Di erent from the existing iterative approaches, our approach via HI does not only maintain small end-user overhead, but also performs iterative bug isolation automatically without developers' intervention, thereby relieving developers of repetitive e orts in isolating bugs. In this paper, we formalize the concept and principles behind the HI technique, and demonstrate its practicality through experimentations. Our experiments show that this new approach via HI saves signi cant instrumentation e ort and sharply reduces runtime overhead, while upholding the accuracy of bug isolation.
- ItemMining Past-Time Temporal Rules(2008-05-27) LO, David; KHOO, Siau-Cheng; LIU, ChaoSpecification mining is a process of extracting specifications, often from program execution traces. These specifications can in turn be used to aid program understanding, monitoring and verification. There are a number of dynamic-analysis-based specification mining tools in the literature, however none so far extract past time temporal expressions in the form of rules stating: ``whenever a series of events occur, previously another series of events happened before''. Rules of this format are commonly found in practice and useful for various purposes. Most rule-based specification mining tools only mine future-time temporal expression. Many past-time temporal rules like ``whenever a resource is used, it was allocated before'' are asymmetric as the other direction does not holds. Hence, there is a need to mine past-time temporal rules. In this paper, we describe an approach to mine significant rules of the above format occurring above a certain statistical thresholds from program exe...
- ItemRequest and Assert: A pragmatic approach to generating specialization scenarios(2006-11-13T07:09:20Z) ZHU, Ping; KHOO, Siau-ChengA specialization scenario provides a programmer friendly mechanism communicating the information about specialization opportunities to partial evaluators. Unfortunately, the process of generating suitable scenarios remains an art only mastered by programmers with in-depth knowledge about partial evaluation. Existing works on generating scenarios either rely on a brute-force approach to generate all possible scenarios, or to introduce specific design patterns into the programming to facilitate extracting specialization scenarios. In this paper, we provide a lightweight approach to partial evaluation by enabling non-experts to declare two simple specialization concerns: request and assert. The request enables a programmer to declare specialization opportunities and an assert aims to prevent undesirable partial evaluation, such as infinite specialization, from occurring. We describe an algorithm that derives specialization scenarios by declaring the necessary binding-time values at program inputs, aiming at fulfilling any request and satisfy the assert meanwhile.
- ItemSMArTIC: Specification Mining Architecture with Trace fIltering and Clustering(2006-08-31) LO, David; KHOO, Siau-ChengImproper management of software evolution, compounded by imprecise, and changing requirements and short time to market requirement, commonly leads to a lack of up-to-date specification. This can result in software that is characterized by presence of bugs, anomalies and even security threats. Software specification mining is a new technique to address this concern by inferring specifications automatically. In this paper, we propose a novel API specification mining architecture called SMArTIC (Specification Mining Architecture with Trace fIltering and Clustering) to improve the accuracy, robustness and scalability of specification miners. This architecture is constructed based on two hypotheses: (1) Erroneous transactions should be pruned from traces input to a miner, and (2) Clustering related traces will localize inaccuracies in learning and reduce over-generalization. Corresponding, SMArTIC comprises four components: an erroneous-trace filtering block, a related-trace clustering block, a learner, and a merger. We show through experiment that the quality of specification miner can be significantly improved using SMArTIC.
- ItemTechnical Indication Generation = Trend Classification + Genetic Algorithm(2005-01-26T03:26:12Z) YAP, Chur Jiun, Bernard; KHOO, Siau-ChengTechnical indicators are used to interpret stock market trends and make investment decisions. The main diffculty of its usage lies in the fact that it is extremely hard to reliably construct an instance of any technical indicators with appropriate parameters for a particular series of stock prices. While genetic algorithm has been used to discover technical indicator in the past, not much justification have been given for such an approach. In this work, we look into the basic assumptions of the working of technical indicators, and the suitability of applying genetic algorithms for indicator discovery. We argue for the use of technical indicator as an approximation to the ideal solutions for daily trading. Consequently, we propose a framework that applies genetic algorithm to discover good parameters for any technical indicators to work well on their respective targeted price trends. A widely used technical indicator, Exponential Moving Average Crossover, is used to illustrate how the proposed framework may be employed to construct good instances of the technical indicator for a targeted price trend.
- ItemA Unified Framework for Partial Evaluation and Program Slicing(2005-01-26T02:33:11Z) ZHU, Ping; KHOO, Siau-ChengThe emphasis on code re-usability in component-based software development has resulted in degradation of system performance. Component specialization techniques have been proposed to overcome this problem. They mainly specialize components wrt contents of component interfaces. This requires specialization to be performed in either a forward or backward direction. The current state of the art applies partial evaluation for forward specialization, but applies backward slicing for backward specialization. In this research, we investigate the relationship between partial evaluation and program slicing in general. We establish a theoretical unified framework in which we can cast both transformations. This framework captures the essence of these two techniques and enables a consistent treatment of program specialization in both forward and backward directions. This framework also make it possible to develop new specialization through cross-fertilization between existing program slicing and partial evaluation techniques.
- ItemVector Abstraction and Concretization for Scalable Detection of Refactorings (A Technical Report)(2014-03-28) MILEA, Narcisa Andreea; JIANG, Lingxiao; KHOO, Siau-ChengAutomated techniques have been proposed to either identify refactoring opportunities (i.e., code fragments that can, but have not yet been restructured in a program), or reconstruct historical refactoring (i.e., code restructuring operations that have happened between di erent versions of a program). However, it remains challenging to apply those techniques to large code bases containing millions of lines of code involving many versions. In this paper, we propose a new scalable technique that can be used for both identifying refactoring opportunities and historical refactoring. The key of our technique is the design of vector abstraction and concretization operations that can capture the essential patterns of the code changes induced by various refactoring operations in the form of characteristic vectors. Thus, the problem of identifying refactorings can be reduced to the problem of identifying matching vectors, which can be solved e ciently. We have implemented our technique for Java. We have applied the prototype to 200 bundle projects from the Eclipse ecosystem containing 4.5 million lines of code, and reports in total more than 32K instances of 17 types refactoring opportunities for all Eclipse projects, taking 25 minutes on average for each type. We have also applied the prototype to 14 versions of 3 smaller programs (JMeter, Ant, XML-Security), and detected (1) more than 2.8K refactoring opportunities within individual versions with an accuracy of about 87%, and (2) more than 190 historical refactorings across consecutive versions of the programs with an accuracy of about 92%.