The Experts below are selected from a list of 8379 Experts worldwide ranked by ideXlab platform
Chungkuan Cheng - One of the best experts on this subject based on the ideXlab platform.
-
area efficient pipelined pseudo Exhaustive Testing with retiming
Design Automation Conference, 1996Co-Authors: Huoyyu Liu, T T Y Lin, Chungkuan ChengAbstract:Pseudo-Exhaustive Testing (PET) offers a simple solution to Testing complex circuits and systems. However, PET suffers long Testing time for test generation and high area overhead of test hardware. The pipelined pseudo-Exhaustive Testing (PPET) achieves fast Testing time with high fault coverage by pipelining test vectors and test responses among partitioned circuit segments. To reduce hardware overhead in PPET, a novel approach for implementing area-efficient PPET is presented. Circuit partitioning with retiming is used to convert designs for PPET. Experimental results show that this approach exhibits an average of 20% area reduction over non-retimed testable circuits. Our algorithm offers high utilization of existing flip-flops and provides a framework for further performance optimization.
-
a study of pipelined pseudo Exhaustive Testing on vlsi circuits with feedback
International Conference on ASIC, 1994Co-Authors: Huoyyu Liou, T T Y Lin, Chungkuan ChengAbstract:An extensive empirical study on feedback paths in pipelined pseudo-Exhaustive Testing (PPET) is conducted. Feedback paths have impact on Testing time for achieving certain fault coverage. Aliasing probability of looped PPET stays in O(2/sup -N/) when N-bit CBITs are used as signature analyzer for test length longer than 2/sup N/ clock cycles. The overall Testing time is then dominated by O(2/sup N/) clock cycles for PPET. Our study proves PPET is an efficient solution for Testing complex circuits and systems. >
-
circuit partitioning for pipelined pseudo Exhaustive Testing using simulated annealing
Custom Integrated Circuits Conference, 1994Co-Authors: Huoyyu Liou, Tingting Lin, Lungtien Liu, Chungkuan ChengAbstract:A novel approach for partitioning circuits with high fan-ins which are not suitable for pseudo-Exhaustive Testing is presented. Circuits under test (CUTs) are modeled as directed graphs and cost function is developed for the optimization algorithm. Disjoint circuit partitions are generated not only for reducing the Exhaustive test length but also for pipelined Testing. Experiments on benchmark circuits demonstrate that simulated annealing produces good results for future applications. >
M A Breuer - One of the best experts on this subject based on the ideXlab platform.
-
novel test pattern generators for pseudo Exhaustive Testing
International Test Conference, 1993Co-Authors: Rajagopalan Srinivasan, Sandeep K S Gupta, M A BreuerAbstract:Pseudo-Exhaustive Testing involves applying all possible input patterns to individual output cones of a circuit. The Testing ensures detection of all combinational faults within individual cones. Test pattern generators based on coding theory principles are not tailored for circuit-under-test and generate inefficient pseudo-Exhaustive test sets. We shall describe novel hardware efficient test pattern generators that employ knowledge of the circuit output cone structures for generating minimal test sets. Using our techniques, we have designed generators that generate minimum test sets for partitioned versions of the combinational benchmark circuits. >
-
an efficient partitioning strategy for pseudo Exhaustive Testing
Design Automation Conference, 1993Co-Authors: Rajagopalan Srinivasan, Sandeep K S Gupta, M A BreuerAbstract:Pseudo-Exhaustive Testing involves applying all possible input patterns to individual output cones of a circuit. Circuits with output cones driven by a large number of inputs often need to be partitioned to reduce the test application time. In this paper, we present an efficient heuristic partitioning procedure of polynomial complexity. Experiments on combinational benchmark circuits validate the efficiency and quality of our approach.
-
a partitioning method for achieving maximal test concurrency in pseudo Exhaustive Testing
VLSI Test Symposium, 1991Co-Authors: Rajagopalan Srinivasan, C A Njinda, M A BreuerAbstract:Pseudo-Exhaustive Testing of combinational circuits usually requires multiple test sessions and/or more than a minimum number of test signals, i.e. unique input sequences. This paper presents a methodology for partitioning combinational circuits such that they can be pseudo-Exhaustively tested with a minimal number of test signals in a single test session. Circuits are logically partitioned during test mode and unrelated inputs are combined to achieve maximal test concurrency. >
Sarfraz Khurshid - One of the best experts on this subject based on the ideXlab platform.
-
bounded Exhaustive test input generation on gpus
Conference on Object-Oriented Programming Systems Languages and Applications, 2017Co-Authors: Ahmet Celik, Sarfraz Khurshid, Sreepathi Pai, Milos GligoricAbstract:Bounded Exhaustive Testing is an effective methodology for detecting bugs in a wide range of applications. A well-known approach for bounded Exhaustive Testing is Korat. It generates all test inputs, up to a given small size, based on a formal specification that is written as an executable predicate and characterizes properties of desired inputs. Korat uses the predicate's executions on candidate inputs to implement a backtracking search based on pruning to systematically explore the space of all possible inputs and generate only those that satisfy the specification. This paper presents a novel approach for speeding up test generation for bounded Exhaustive Testing using Korat. The novelty of our approach is two-fold. One, we introduce a new technique for writing the specification predicate based on an abstract representation of candidate inputs, so that the predicate executes directly on these abstract structures and each execution has a lower cost. Two, we use the abstract representation as the basis to define the first technique for utilizing GPUs for systematic test generation using executable predicates. Moreover, we present a suite of optimizations that enable effective utilization of the computational resources offered by modern GPUs. We use our prototype tool KoratG to experimentally evaluate our approach using a suite of 7 data structures that were used in prior studies on bounded Exhaustive Testing. Our results show that our abstract representation can speed up test generation by 5.68 times on a standard CPU, while execution on a GPU speeds up the execution, on average, by 17.46 times.
-
towards Exhaustive Testing of websites using jpf
ACM Sigsoft Software Engineering Notes, 2017Co-Authors: Sarvesh V Nagarajan, Nastaran Shafiei, Sarfraz KhurshidAbstract:In this paper, we present a framework for Exhaustive test input generation and execution of tests for websites using JPF, and Java libraries such as Selenium and JUnit. Specifically, we utilize the core functionality of jpf-nhandler, a JPF extension, to enable use of useful Java libraries such as GSON in the JPF environment. The paper further describes iterating through webpages successively and generating test inputs systematically for each page. It also presents the experimental results of running our framework on a small example website and a real-world website
-
software assurance by bounded Exhaustive Testing
IEEE Transactions on Software Engineering, 2005Co-Authors: David Coppit, Sarfraz Khurshid, Jinlin Yang, Kevin SullivanAbstract:Bounded Exhaustive Testing (BET) is a verification technique in which software is automatically tested for all valid inputs up to specified size bounds. A particularly interesting case of BET arises in the context of systems that take structurally complex inputs. Early research suggests that the BET approach can reveal faults in small systems with inputs of low structural complexity, but its potential utility for larger systems with more complex input structures remains unclear. We set out to test its utility on one such system. We used Alloy and TestEra to generate inputs to test the Galileo dynamic fault tree analysis tool, for which we already had both a formal specification of the input space and a test oracle. An initial attempt to generate inputs using a straightforward translation of our specification to Alloy did not work well. The generator failed to generate inputs to meaningful bounds. We developed an approach in which we factored the specification, used TestEra to generate abstract inputs based on one factor, and passed the results through a postprocessor that reincorporated information from the second factor. Using this technique, we were able to generate test inputs to meaningful bounds, and the inputs revealed nontrivial faults in the Galileo implementation, our specification, and our oracle. Our results suggest that BET, combined with specification abstraction and factoring techniques, could become a valuable addition to our verification toolkit and that further investigation is warranted.
-
software assurance by bounded Exhaustive Testing
International Symposium on Software Testing and Analysis, 2004Co-Authors: Kevin Sullivan, Sarfraz Khurshid, Jinlin Yang, David Coppit, Daniel JacksonAbstract:The contribution of this paper is an experiment that shows the potential value of a combination of selective reverse engineering to formal specifications and bounded Exhaustive Testing to improve the assurance levels of complex software. A key problem is to scale up test input generation so that meaningful results can be obtained. We present an approach, using Alloy and TestEra for test input generation, which we evaluate by experimental application to the Galileo dynamic fault tree analysis tool.
-
an evaluation of Exhaustive Testing for data structures
2003Co-Authors: Darko Marinov, Alexandr Andoni, Dumitru Daniliuc, Sarfraz Khurshid, Martin RinardAbstract:We present an evaluation of Exhaustive Testing of linked data structures with sophisticated structural constraints. Specifically, we use the Korat Testing framework to systematically enumerate all legal inputs within a certain size. We then evaluate the quality of this test suite according to several measurements: ability to detect injected faults in the original correct implementations, code coverage, and specification coverage. Our results indicate that it is feasible to use Exhaustive Testing to obtain, within a reasonable amount of time, a high-quality test suite that can detect almost all faults and achieve complete code and specification coverage. Moreover, our results show that our Exhaustive tests are of higher quality than randomly selected test suites that contain the same number of inputs selected from a larger potential input set. We conclude that Exhaustive Testing is a practical and effective Testing methodology for sophisticated linked data structures.
Darko Marinov - One of the best experts on this subject based on the ideXlab platform.
-
repok based reduction of bounded Exhaustive Testing
Software Testing Verification & Reliability, 2014Co-Authors: Darko Marinov, Nazareno Aguirre, Marcelo F Frias, Valeria BengoleaAbstract:While the effectiveness of bounded Exhaustive test suites increases as one increases the scope for the bounded Exhaustive generation, both the time for test generation and the time for test execution grow exponentially with respect to the scope. In this article, a set of techniques for reducing the time for bounded Exhaustive Testing, by either reducing the generation time or reducing the obtained bounded Exhaustive suites, is proposed. The representation invariant of the software under test's input, implemented as a repOK routine, is exploited for these reductions in two ways: i to factor out separate representation invariants for disjoint structures of the inputs; and ii to partition valid inputs into equivalence classes, according to how these exercise the repOK code. The first is used in order to split the test input generation process, as disjoint substructures can be independently generated. The second is used in order to reduce the size of a bounded Exhaustive test suite, by removing from the suite those tests that are equivalent to some tests already present in the suite. Copyright © 2014 John Wiley & Sons, Ltd.
-
reducing the costs of bounded Exhaustive Testing
Fundamental Approaches to Software Engineering, 2009Co-Authors: Vilas Jagannath, Yun Young Lee, Brett Daniel, Darko MarinovAbstract:Bounded-Exhaustive Testing is an automated Testing methodology that checks the code under test for all inputs within given bounds: first the user describes a set of test inputs and provides test oracles that check test outputs; then the tool generates all the inputs, executes them on the code under test, and checks the outputs; and finally the user inspects failing tests to submit bug reports. The costs of bounded-Exhaustive Testing include machine time for test generation and execution (which translates into human time waiting for these results) and human time for inspection of results. This paper proposes three techniques that reduce these costs. Sparse Test Generation skips some tests to reduce the time to the first failing test. Structural Test Merging generates a smaller number of larger test inputs (rather than a larger number of smaller test inputs) to reduce test generation and execution time. Oracle-based Test Clustering groups failing tests to reduce the inspection time. Results obtained from the bounded-Exhaustive Testing of the Eclipse refactoring engine show that these three techniques can substantially reduce the costs while mostly preserving fault-detection capability.
-
an evaluation of Exhaustive Testing for data structures
2003Co-Authors: Darko Marinov, Alexandr Andoni, Dumitru Daniliuc, Sarfraz Khurshid, Martin RinardAbstract:We present an evaluation of Exhaustive Testing of linked data structures with sophisticated structural constraints. Specifically, we use the Korat Testing framework to systematically enumerate all legal inputs within a certain size. We then evaluate the quality of this test suite according to several measurements: ability to detect injected faults in the original correct implementations, code coverage, and specification coverage. Our results indicate that it is feasible to use Exhaustive Testing to obtain, within a reasonable amount of time, a high-quality test suite that can detect almost all faults and achieve complete code and specification coverage. Moreover, our results show that our Exhaustive tests are of higher quality than randomly selected test suites that contain the same number of inputs selected from a larger potential input set. We conclude that Exhaustive Testing is a practical and effective Testing methodology for sophisticated linked data structures.
Daniel Jackson - One of the best experts on this subject based on the ideXlab platform.
-
software assurance by bounded Exhaustive Testing
International Symposium on Software Testing and Analysis, 2004Co-Authors: Kevin Sullivan, Sarfraz Khurshid, Jinlin Yang, David Coppit, Daniel JacksonAbstract:The contribution of this paper is an experiment that shows the potential value of a combination of selective reverse engineering to formal specifications and bounded Exhaustive Testing to improve the assurance levels of complex software. A key problem is to scale up test input generation so that meaningful results can be obtained. We present an approach, using Alloy and TestEra for test input generation, which we evaluate by experimental application to the Galileo dynamic fault tree analysis tool.