Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Efficient branch and node testing

Misurda, Jonathan (2012) Efficient branch and node testing. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Primary Text

Download (1MB) | Preview


Software testing evaluates the correctness of a program’s implementation through a test suite. The quality of a test case or suite is assessed with a coverage metric indicating what percentage of a program’s structure was exercised (covered) during execution. Coverage of every execution path is impossible due to infeasible paths and loops that result in an exponential or infinite number of paths. Instead, metrics such as the number of statements (nodes) or control-flow branches covered are used.

Node and branch coverage require instrumentation probes to be present during program runtime. Traditionally, probes were statically inserted during compilation. These static probes remain even after coverage is recorded, incurring unnecessary overhead, reducing the number of tests that can be run, or requiring large amounts of memory

In this dissertation, I present three novel techniques for improving branch and node coverage performance for the Java runtime. First, Demand-driven Structural Testing (DDST) uses dynamic insertion and removal of probes so they can be removed after recording coverage, avoiding the unnecessary overhead of static instrumentation. DDST is built on a new framework for developing and researching coverage techniques, Jazz. DDST for node coverage averages 19.7% faster than statically-inserted instrumentation on an industry-standard benchmark suite, SPECjvm98.

Due to DDST’s higher-cost probes, no single branch coverage technique performs best on all programs or methods. To address this, I developed Hybrid Structural Testing (HST). HST combines different test techniques, including static and DDST, into one run. HST uses a cost model for analysis, reducing the cost of branch coverage testing an average of 48% versus Static and 56% versus DDST on SPECjvm98.

HST never chooses certain techniques due to expensive analysis. I developed a third technique, Test Plan Caching (TPC), that exploits the inherent repetition in testing over a suite. TPC saves analysis results to avoid recomputation. Combined with HST, TPC produces a mix of techniques that record coverage quickly and efficiently.

My three techniques reduce the average cost of branch coverage by 51.6–90.8% over previous approaches on SPECjvm98, allowing twice as many test cases in a given time budget.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Misurda, Jonathanjmisurda@cs.pitt.eduJRMST106
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairChilders, Bruce R.childers@cs.pitt.eduCHILDERS
Committee MemberChrysanthis, Panos K.panos@cs.pitt.eduPANOS
Committee MemberSoffa, Mary
Committee MemberZhang, Youtaozhangyt@cs.pitt.eduYOUTAO
Date: 1 February 2012
Date Type: Publication
Defense Date: 29 November 2011
Approval Date: 1 February 2012
Submission Date: 2 December 2011
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Number of Pages: 152
Institution: University of Pittsburgh
Schools and Programs: Dietrich School of Arts and Sciences > Computer Science
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: Structural Testing, Demand-driven Instrumentation, Software Testing, Coverage, Testing, Branch Coverage, Node Coverage
Date Deposited: 01 Feb 2012 13:34
Last Modified: 15 Nov 2016 13:35


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item