Bit Rate of Programs
This work addresses the challenge of analyzing program behavior for testing and understanding information characteristics, particularly in black-box scenarios, but appears incremental as it builds on existing concepts like Shannon information and signal processing.
The paper tackles the problem of measuring the information rate (bit rate) of program executions, treating them as discrete time signals, and provides algorithms for identifying information-rich components in finite state systems and proposes a bit rate signal and spectrum for black-box programs using data compression and Fourier transform.
A program can be considered as a device that generates discrete time signals, where a signal is an execution. Shannon information rate, or bit rate, of the signals may not be uniformly distributed. When the program is specified by a finite state transition system, algorithms are provided in identifying information-rich components. For a black-box program that has a partial specification or does not even have a specification, a bit rate signal and its spectrum are studied, which make use of data compression and the Fourier transform. The signal provides a bit-rate coverage for testing the black-box while its spectrum indicates a visual representation for execution's information characteristics.