Combinatorial testing has been shown to be a very effective strategy for software testing. After a failure is detected, the next task is to identify one or more faulty statements in the source code that have caused the failure. In this paper, we present a fault localization approach, called BEN, which produces a ranking of statements in terms of their likelihood of being faulty by leveraging the result of combinatorial testing. BEN consists of two major phases. In the first phase, BEN identifies a combination that is very likely to be failure-inducing. A combination is failure-inducing if it causes any test in which it appears to fail. In the second phase, BEN takes as input a failure-inducing combination identified in the first phase and produces a ranking of statements in terms of their likelihood to be faulty. We conducted an experiment in which our approach was applied to the Siemens suite and four real-world programs, flex, grep, gzip and sed, from Software Infrastructure Repository (SIR). The experimental results show that our approach can effectively and efficiently localize the faulty statements in these programs.

Profit-driven cyber-criminals are motivated to prolong Android malware's lifetime by hiding malicious behaviors from raising suspicion. Stealthy malware has become an emerging challenge to Android security as it can remain undetected for quite a long time. However, traditional defense techniques are insufficient in face of this new threat. Our in-depth study on published malware analysis reports and corresponding code analysis leads to three key observations: 1) a stealthy attack goes through multiple states; 2) state transitions are caused by a sequence of attack actions; 3) an attack action typically involves several Android APIs on different objects.

In server applications, threads are created to handle incoming requests. Since threads consume significant resources including CPU cycles and memory, it is important to control the number of threads that are created. In this paper, we introduce a lightweight, static approach to detecting unbounded thread- instantiation loops that may exist in a server application. The key observation of our approach is that threads are objects of special significance and the decision logic for thread instantiation is typically not complex. Our approach checks loops against some bounded thread-instantiation patterns. A loop is considered bounded if a pattern match is found. Otherwise, it is considered unbounded. Our approach is heuristic by nature. That is, it does not guarantee to detect all the unbounded loops and may report unbounded loops that are actually bounded. To evaluate the effectiveness of our approach, we report an Eclipse plugin called ThreadBoundChecker which implements our approach and an experiment on 24 real-life Java server applications. The results of our evaluation show that our approach can effectively detect unbounded thread-instantiation loops in these applications. In particular, 12 unbounded thread-instantiation loops detected by our approach are confirmed by the original developers.

Combinatorial testing has been shown to be a very effective testing strategy. After a failure is detected, the next task is to identify the fault that causes the failure. In this paper, we present an approach to fault localization that leverages the result of combinatorial testing. Our approach is based on a notion called failure-inducing combinations. A combination is failure-inducing if it causes any test in which it appears to fail. Given a failure-inducing combination, our approach derives a group of tests that are likely to exercise similar traces but produce different outcomes. These tests are then analyzed to locate the faults. We conducted an experiment in which our approach was applied to the Siemens suite as well as the grep program from the SIR repository that has 10068 lines of code. The experimental results show that our approach can effectively and efficiently localize the faults in these programs.

Buffer overflow vulnerabilities are program defects that can cause a buffer to overflow at runtime. Many security attacks exploit buffer overflow vulnerabilities to compromise critical data structures. In this paper, we present a black-box testing approach to detecting buffer overflow vulnerabilities. Our approach is motivated by a reflection on how buffer overflow vulnerabilities are exploited in practice. In most cases the attacker can influence the behavior of a target system only by controlling its external parameters. Therefore, launching a successful attack often amounts to a clever way of tweaking the values of external parameters. We simulate the process performed by the attacker, but in a more systematic manner. A novel aspect of our approach is that it adapts a general software testing technique called combinatorial testing to the domain of security testing. In particular, our approach exploits the fact that combinatorial testing often achieves a high level of code coverage. We have implemented our approach in a prototype tool called Tance. The results of applying Tance to five open-source programs show that our approach can be very effective in detecting buffer overflow vulnerabilities.

Security testing has gained significant attention recently due to frequent attacks against software systems. This paper presents a trace-based security testing approach. It reuses test cases generated from previous testing methods to produce execution traces. An execution trace is a sequence of program statements exercised by a test case. Each trace is symbolically executed to produce program constraints and security constraints. A program constraint is a constraint imposed by program logic on program variables. A security constraint is a condition on program variables that must be satisfied to ensure system security. A security flaw exists if there is an assignment of values to program variables that satisfies the program constraint but violates the security constraint. This approach detects security flaws even if existing test cases do not trigger them. The novelty of this method is a test model that unifies program constraints and security constraints such that formal reasoning can be applied to detect vulnerabilities. A tool named SecTAC is implemented and applied to 14 benchmark programs and 3 open-source programs. The experiment shows that SecTAC quickly detects all reported vulnerabilities and 13 new ones that have not been detected before.

Traditional test case generation methods usually consider coverage criteria like statement or path coverage and ignore security characteristics. The result is that a test case may fail to find vulnerabilities even if it covers the vulnerable statements. However, we argue that existing test cases are still of great value because significant human effort and time have been invested to achieve high coverage criteria. A high coverage indicates a high possibility that vulnerable statements occur in the execution traces of these test cases. Thus existing test cases could guide us to those vulnerable statements. Under this intuition, we present a method of security testing by re-examining existing test cases. The basic idea is to discover two types of constraints in a program: program constraints (PC) and security constraints (SC). The former are the constraints imposed by program statements. For example, an assignment statement i=0 constrains the value of i to be 0. The later are the constraints derived from security concerns. For example, a buffer should never be overflowed. Intuitively, a statement is vulnerable if it can make PCrarrSC be false, which means the program constraints are not strict enough to ensure the security constraints. We design and develop a tool named RETAST to demonstrate our idea and the initial result is promising.

Abstract One approach to testing concurrent programs is called reachability testing, which derives test sequences automatically and on‐the‐fly, without constructing a static model. Existing reachability testing algorithms are exhaustive in that they are intended to exercise all possible synchronization sequences of a concurrent program with a given input. In this paper, we present a new testing strategy, calledt‐way reachability testing, that adopts the dynamic framework of reachability testing but selectively exercises a subset of synchronization sequences. The selection of the synchronization sequences is based on a combinatorial testing strategy calledt‐way testing. We present an algorithm that implementst‐way reachability testing, and report the results of several case studies that were conducted to evaluate its effectiveness. The results indicate thatt‐way reachability testing can substantially reduce the number of synchronization sequences exercised during reachability testing while still effectively detecting faults. Copyright © 2007 John Wiley & Sons, Ltd.

We have proposed inductive model checking (IMC) to alleviate the state explosion problem in model checking. IMC divides the whole verification tasks into several sub-tasks, and applies the three inductive steps (basis, hypothesis, and induction) to verify a system with model checking. In this paper, we continue our research by determining those temporal formulas, namely, persistent temporal formulas, which are verifiable with IMC. One important characteristic of a persistent temporal formula is that it contains a periodic temporal formula that must be held persistently. From the verification results of the periodic formula with different sequences of states, IMC concludes the verification of the persistent temporal formula

A Java monitor is a Java class that defines one or more synchronized methods. Unlike a regular object, a Java monitor object is intended to be accessed by multiple threads simultaneously. Thus, testing a Java monitor can be significantly different from testing a regular class. In this paper, we propose a state exploration-based approach to testing a Java monitor. A novel aspect of our approach is that during exploration, threads are introduced on-the-fly, and as needed, to simulate race conditions that can occur when multiple threads try to access a monitor object at the same time. Furthermore, each transition is defined in a way such that the behavior of the threads along each path can be precisely characterized and controlled. We describe a prototype tool called MonitorExplorer and report three case studies that are designed to provide an initial evaluation of our approach

Reachability analysis is a commonly used approach to protocol validation, but it suffers from the well-known state explosion problem. In this paper, we present a new approach to reachability analysis called blocking-based simultaneous reachability analysis (or BSRA). A central notion in BSRA is that of a global blocking point. Instead of exploring every global state, BSRA only explores a set of global blocking points, which usually account for a small portion of the state space. We show how to use BSRA to detect several commonly found logical errors. Our experimental results demonstrate that BSRA can significantly reduce the number of states explored during protocol validation.

One common approach to protocol validation is reachability analysis, which involves systematically exploring the state space of a protocol. The main challenge of reachability analysis is dealing with the state explosion problem. In this paper, we present a new reachability analysis approach, called blocking-based simultaneous reachability analysis, for protocol validation. This approach has the potential to significantly reduce the number of states that have to be explored but can still be used to detect several logical errors that are commonly found in a protocol.

In recent years, Web applications have grown so quickly that they have already become crucial to the success of businesses. However, since they are built on Internet and open standard technologies, Web applications bring new challenges to researchers, such as dynamic behaviors, heterogeneous representations, novel control flow and data flow mechanisms, etc. In this paper, we propose an agent-based approach for Web application testing. While the agent-based framework greatly reduces the complexity of Web applications, a four-level dataflow test approach can be employed to perform structure testing on them. In this approach, data flow analysis is performed as function level testing, function cluster level testing, object level testing, and Web application level testing, from low abstract level to high abstract level. Each test agent in the framework takes charge of the testing in an abstract level for a particular type of Web document or object.

The development of multiagent systems (MAS) is not a trivial task. In addition, with the advances in Internet technologies, MAS are undergoing a transition from closed to open architectures composed of a huge number of autonomous agents, which operate and move across different environments. In fact, openness introduces additional complexity to the system modeling, design and implementation. It also impacts on most quality attributes of MAS, including scalability, interoperability, reliability and adaptability. This paper brings together researchers and practitioners to discuss the current state and future direction of research in software engineering for open MAS. A particular interest is to understand those issues in the agent technology that make it difficult and/or improve the production of large open systems.

The popularity of agent-based systems has increased rapidly in recent years. A number of software engineering frameworks/methodologies have been proposed to support multi-agent systems construction. How well are software engineering methodologies in support of multi-agent systems development? What are the strengths and weaknesses of such attempts? In this paper, we report our experience from the application of a software engineering framework for multi-agent systems. The framework is rooted in the belief desire intention (BDI) formalism and an extension of the Unified Modeling Language (UML). Our focus is to present lessons learned by applying this framework to an agent-based intelligent elevator system. We also identify some research issues.

In recent years, Web applications have grown rapidly because of their abilities to provide online information access to anyone at anytime around the world. As Web applications become complex, there is a growing concern about their quality and reliability. This paper extends traditional data flow testing techniques to Web applications. Several data flow issues about analyzing HyperText Markup Language (HTML) documents in Web applications are discussed. An object-based data flow testing approach is presented. The approach is based on a test model that captures data flow test artifacts of Web applications. In the test model, each entity of a Web application is modeled as an object. The data flow information of the functions within an object or across objects is then captured using various flow graphs. Based on the object-based test model, data flow test cases for a Web application can be systematically and selectively generated in five different levels.

Recently the number of Web applications has increased immensely. Many businesses have been using Web applications for their mission-critical operations. As Web applications become complex, their quality and reliability become crucial. The paper describes an object oriented test model that captures both structural and behavioral test artifacts of Web applications. The model represents the entities of Web applications as objects and describes their structures, relationships, and dynamic behaviors. Based on the test model, test methods are presented to derive test cases automatically for ensuring the structures and behaviors of Web applications.

In recent years, Web applications have become prevalent around the world. Many companies have developed or integrated their mission-critical applications using Web technologies. As Web applications become more complex, testing Web applications becomes crucial. We extend data flow testing techniques to Web applications. Several data flow issues for analyzing HTML and eXtensible Markup Language (XML) documents in Web applications are discussed. An approach to supporting data flow testing for Web applications is presented. In our approach, the structural test artifacts of a Web application are captured in a Web Application Test Model (WATM) where each component of the Web application is treated as an object. The elements of an HTML or XML document are considered as structured variables within an object. Data flow test cases for Web applications are derived from flow graphs in five levels according to the types of definition-use chains for the variables of interest.

Object Behavior Logic (OBL) is proposed in order to specify object oriented system behavior. An inference engine is introduced for verifying the consistency of the systems based on the specification in OBL. OBL uses the paradigms of state machine to catch the dynamic aspect of object oriented systems in formal specification, plus the features of object oriented concepts such as inheritance, instantiation, and so forth, which separate the unique object oriented techniques from the function oriented techniques.

Brooks' law says that adding manpower to a late software project makes it later. F.P. Brooks Jr. (1995) developed the law through observation of many projects and derived the generalization. His explanation was quite reasonable and convincing. However, it becomes a debilitating statement to any software project manager who is faced with a late project. This paper presents an in-depth study of Brooks' law using the system dynamics simulation approach. Unlike the first-order approximation of Brooks' law, we found some interesting results that can benefit practicing project managers. We found that adding people to a late project will always increase its cost, but the project may not always be late. Only under a certain degree of sequential constraints among the project tasks will the project be delayed. To investigate the impact of sequential constraints, we simulated numerous task conditions and found that there is a time-line T for each project which means that, if enough manpower is added before T, the project still can finish before the scheduled deadline. If the manpower adjustment is after T, then the project will definitely be late. In this way, Brooks' law is revised and turned into a useful guiding principle to benefit software development.

In this paper, we present a dynamic state testing approach for a reusable CORBA component by constructing perception-based state machines and a state-based replay system in the CORBA environment. The state machines are constructed based on the perceptions of the remote component used in our application. Based on the state machine, we also design a program replay system to make the testing deterministic since CORBA components have nondeterministic execution behavior which makes testing inefficient ineffective and not reproducible. With our testing approach, testers can detect state behavioral errors of an uncertain reusable component dynamically and deterministically in the CORBA environment.

Incremental delivery (ID) is a software development paradigm which advocates that systems be delivered to end users in usable, useful and semi-independent increments. ID differs from the traditional development paradigm, which we call monolithic delivery (MD), in which a software system is considered as a monolithic, inseparable whole delivered as one unit. The purpose of this study is to compare the ID and MD approaches in terms of their maintenance efforts through an analytical parametric study. The results of the study provide insight into how incremental delivery can be employed to reduce software maintenance effort. © 1998 John Wiley & Sons, Ltd.

No abstract available.

The object-orientated paradigm provides the power for software development but at the same time introduces some brand new problems. One of these problems is that the relationships among classes are more complex and difficult to identify than those in the traditional paradigm. This problem becomes a major obstacle for regression testing of OO software, in which the relationships among classes as well as those between test cases and classes, must be determined a priori. In this paper we propose a new method to select only a fraction of the test cases from the entire test suite to revalidate an OO software system. This method is based on the concepts of class firewall and of marking all the classes ‘touched’ by a test case. From the class firewall, we can identify all of the affected classes after a new version of software is released. Together with the markings, we can also identify all the test cases in the test suite that need to be retested after the software change. A step-by-step process is proposed to identify the relationships between classes and test cases, compute the class firewall, and select only the appropriate test cases for retesting. © 1997 John Wiley & Sons, Ltd.

This paper presents a history-based approach to detect class faults that a test set may fail to uncover. The method sequence test history contains the run-time information about object states, state transitions, and dependence relations between data members. The approach examines the test history to determine if some faulty state (or new state) is reachable from the states that have been covered by the test set. The main benefit of the approach is that it only depends on the existing test set that has been executed, and hence it does not require the development of any new test case.

An object-oriented real time systems conceptual modeling approach is described. In this approach, each object is specified by an object type, consisting of supertypes (inheritance), component types (aggregation), attributes, operations, static constraints, and temporal constraints. That is, an object type specification defines a theory of a type of objects. An object-oriented real time conceptual model using the object types can be translated into an augmented Petri net with timing and temporal constraints. A reachability tree of permissible system states is generated for the augmented Petri nets for verifying whether the conceptual model satisfies desired temporal constraints.

Object state behavior implies that the effect of an operation on an object may depend on the states of the object and other objects. It may cause state changes to more than one object. Thus, the combined or composite effects of the object operations must be analyzed and tested. We show that certain object state behavior errors cannot be detected readily by conventional testing methods. We describe an object state test method consisting of an object state model, a reverse engineering tool, and a composite object state testing tool. The object state test model is an aggregation of hierarchical, concurrent, communicating state machines envisioned mainly for object state testing. The reverse engineering tool produces an object state model from any C++ program. The composite object state testing tool analyzes the object state behaviors and generates test cases for testing object state interactions. We show the detection of several composite object state behavior errors that exist in a well-known thermostat example.

Since polymorphism in object-orientated (OO) programming is an important feature and tool to increase the reusability and extensibility of object-orientated programs, understanding and identifying polymorphism changes and their impacts in an object-orientated program is very important in software maintenance. Although many published research articles have addressed the polymorphism feature in object-orientated programs, almost none of them have discussed software maintenance issues on identification of polymorphism change and impact. This paper proposes a formal software maintenance model for polymorphism in object-orientated programs, and discusses a systematic approach to track different polymorphism changes and their ripple effects. In addition, it reports on the implementation of a relevant tool, OOTME, and its use on two case studies.

Since class objects are the major components in object oriented (OO) programs during run time, testing the behavior of these objects become an important task in testing of object oriented programs to complement other types of testing, such as, structure testing and functional testing. To check the behavior of objects in OO programs, it is essential to check each state and each transition for every object. The paper proposes a new test model, called object state diagram, to capture and represent the dynamic behavior of objects in an OO program. The model is an extension of the existing state models, it supports basic OO features, such as class objects, inheritance, aggregation and overloading. Unlike other models, it is a concurrent, communicating state machine which has the capability of representing the object state hierarchy for a complex class object. Based on this model we address the issues and solutions to object state test strategy, test criteria and test generation.

The complexity and interdependencies of an object oriented program makes testing of such programs difficult. We present a reverse engineering based model called Object Relation Diagram (ORD), which is generated from analyzing the C++ source code of an object oriented program. An ORD is a directed graph in which the vertices represent the object classes and the edges represent the relationships among the object classes. Based on the ORD, a test strategy, called test order, for unit testing and integration testing of object oriented programs is described. The test order algorithm uses topological sorting and clusters of strongly connected subgraphs of the ORD. It computes the optimal test order in the sense that the effort required to construct the test stubs to simulate the untested classes/member functions is minimum. We show the savings of the test strategy through statistics of the InterViews library.

Software development techniques have seen significant progress since the 1960s. Most research accomplishments have been in software development but not in software maintenance. This is also true for the object-oriented paradigm. We believe that the features of object-oriented approach have a significant impact on maintainability. We report an incipient study indicating that the architecture of an object-oriented system indeed affects its maintainability. This is attributed to the structure of its inheritance hierarchy, among other factors. We also attempt to provide some rationale behind this phenomenon. The possible tension between object reuse and the maintainability of its product is also discussed in the paper.

Acceptance testing is the determining factor in the satisfaction of the contract between the software vendor and the customer. In today's industry practice, there is a lack of a systematic method to help testers (or customers) construct, formalize, and verify acceptance testing models, and use them for automatic test case generation. This paper proposes a systematic approach to form the acceptance test model for a software system to represent its external behavior from the users' perspectives. Based on the generated test model, different rigorous acceptance test criteria are defined, and various types of acceptance testing are discussed.>

The importance of object state testing is illustrated through a simple example. We show that certain errors in the implementation of object state behavior cannot be readily detected by conventional structural testing, functional testing, and state testing. We describe an object state test model and outline a reverse engineering method for extracting object state behaviors from C++ source code. The object state test model is a hierarchical, concurrent, communicating state machine. It resembles the concepts of inheritance and aggregation in the object-oriented paradigm rather than the concept of state decomposition as in some existing models. The reverse engineering method is based on symbolic execution to extract the states and effects of the member functions. The symbolic execution results are used to construct the state machines. The usefulness of the model and of the method is discussed in the context of object state testing in the detection of a state behavior error. >

Object-oriented conceptual modeling captures real world entities as close as possible. Data and functions on encapsulated in an object. This allows software to be easily adapted to changes in the application. We present an object-oriented approach for modeling and analysis of time dependent systems. It describes the structural aspect and the time critical behavioral aspect of objects in one model and from which formal analysis can be conducted to verify desirable properties. In particular, the main concern of behavioral modeling is to present the specification of temporal knowledge about object activities such as their chronological ordering, durations, and time limits.>

In the object-oriented (OO) paradigm, new features (such as encapsulation, aggregation, inheritance, polymorphism and dynamic binding) introduce new problems in software testing and maintenance. One of them is the difficulty of identifying the affected components (such as classes) when changes are made in object-oriented class libraries or programs. This paper discusses the types of code changes in an object-oriented class library, and provides an automated solution to identify different kinds of code changes and their impact. In addition, an OO software maintenance environment that implements the research result is described. Our experience with the environment prototype shows promising results.>

Article Free Access Share on On verification of database temporal constraints Author: C. H. Kung Dept of Computer Science, The Norwegian Institute of Technology, Tiondheim, NORWAY Dept of Computer Science, The Norwegian Institute of Technology, Tiondheim, NORWAYView Profile Authors Info & Claims SIGMOD '85: Proceedings of the 1985 ACM SIGMOD international conference on Management of dataMay 1985 Pages 169–179https://doi.org/10.1145/318898.318911Online:01 May 1985Publication History 18citation397DownloadsMetricsTotal Citations18Total Downloads397Last 12 Months8Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF