Browse Prior Art Database

Tool for Automatic Input Reduction Disclosure Number: IPCOM000023323D
Original Publication Date: 2004-Mar-30
Included in the Prior Art Database: 2004-Mar-30
Document File: 2 page(s) / 62K

Publishing Venue



Finding the minimal set of input that generates a specific output given a starting input set is a common activity, especially during debugging. Typically, this is done in an ad-hoc manner by a human user repeatedly removing sections of the input and running the program with the altered input. This is both time consuming and error prone in that a mistake may require starting from scratch with the original input. This invention automates the process of reducing input to a program or process that shows specific program behaviour. We describe a tool that systematically removes sections of input while maintaining specific program behaviour which does not require human intervention. This tool will free the user from this task, producing more consistent and faster results.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 2

Tool for Automatic Input Reduction

The tool works by dividing the input into units called regions, which are considered indivisible. For example, this may be at the level of declarations in a programming language. These regions are grouped into progressively smaller blocks which are individually removed with the remainder of the input being tested against the adjusted symptom. Continuing the previous example, removing a block of input may result in an error message having different coordinates when issued by a compiler. Regions that can be successfully removed while maintaining the specific program behaviour are removed, resulting in a smaller input that still produces the specific behaviour. The following pseudo-code illustrates the process.

divideInput(input, regions, N) {

// Divide the input into units which are considered indivisible and assign the units
into the regions array. // takes input, sets array regions, sets value N

// For example, divide C program into individual declarations

N = number of atomic units in input

i = 1

while (i <= N) {

regions[i] = unit[i];

i = i + 1;



adjust(symptom, oldInput, newInput) {

// Adjust the expected symptom based on the change to the input

// takes symptom, takes the original input, takes the new input, returns the new
adjusted symptom.

// For example, adjust coordinates of error message produced by compiler (which may
be no change)

newSymptom = expected change in behaviour for using newInput instead of oldInput

return newSymptom;

check(input, symptom) {

// Run the program (or process) on the input and look for the symptom.

// takes the current input, takes the symptom, returns true if the symptom was
reproduced, false otherwise.

// For example,...