First Advisor

Xiaoyu Song

Term of Graduation

Summer 2021

Date of Publication

8-16-2021

Document Type

Dissertation

Degree Name

Doctor of Philosophy (Ph.D.) in Electrical and Computer Engineering

Department

Electrical and Computer Engineering

Language

English

Subjects

Software engineering

DOI

10.15760/etd.7633

Physical Description

1 online resource (ix, 117 pages)

Abstract

Statistical structural testing(SST) is an effective testing technique that produces random test inputs from probability distributions. SST shows superiority in fault-revealing power over random testing and deterministic approaches since it heritages the merits from both of them. SST ensures testing thoroughness by setting up a probability lower-bound criterion for each structural cover element and test inputs that exercise a structural cover element sampled from the probability distribution, ensuring testing randomness. Despite the advantages, SST is not a widely used approach in practice. There are two major limitations. First, to construct probability distributions, a tester must understand the underlying software's structure, which is difficult to obtain in the real-world testing scenario. Although automated search is able to construct probability distributions iteratively, the efficiency remains unsatisfiable. Second, SST is limited to unit testing or programs with small structural complexity.

The first research objective is to analyze the root cause of the unsatisfiable efficiency. It turns out that a strong statistical structural coverage criterion results in a high impact of the noisy fitness estimation. Hence, we proposed a weakened criterion that can significantly reduce the search time without the loss of substantial fault-detecting power. We also developed a search algorithm called CACOR that resists the noisy fitness influence. The input distribution model harnesses a set of weighted uniform distributions over the input domain space, which is enumerated effectively by the constrained ant colony optimization strategies. Experimental studies demonstrate the excellent search performance of the CACOR algorithm and the high-grade fault-detecting ability of the input distributions produced by the algorithm.

The second research objective is to apply the SST strategy to the real-world testing industries. The mutation-based fuzzing technique (e.g., AFL) has enjoyed great success due to the automation of the testing process and, more importantly, the ability to discover critical vulnerabilities. The role of SST in the fuzzer is a test input provider when AFL is stuck in discovering new program paths. We noticed that AFL is often stuck in testing the code structures with deeply nested conditions and scanty input sub-domain spaces. AFL's mutation strategy often produces inputs that stay in the same or upper condition level and hardly trigger the deeper level. For scanty input subdomain space, AFL acts as random testing. We perform a comprehensive search to construct input distribution such that both of the outgoing edges of a conditional statement are guaranteed to be triggered with a probability lower bounds threshold. The experimental study demonstrates that the lead time to discover bugs with SST is significantly decreased.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Persistent Identifier

https://archives.pdx.edu/ds/psu/36280

Download

Share

COinS