Topic: consistency testing

topics > computer science > programming > Group: testing

exception handling
program proving
type checking

automated tests of specifications and designs
compiler error checking
database agents
database consistency and reliability
debugging by usage rules
debugging techniques
defensive programming
dependency analysis
dynamic type checking
error safe systems
exceptions and undesired events
error checking in robot programming
file system reliability
flavor analysis and typestates for supplementary type checking
Goldstine and von Neumann consistency proof
model checker
path expression
program proof via assertions
program proving is infeasible
proof-carrying code
quality assurance
range checking
resourceful, redundant systems for reliability
run-time assertions
safety, liveness, and system properties
self-identifying data structures
testing by voting or N-version
type-safe and secure languages


Most program errors result in the breakdown of a data structure or a relationship between data structures. By detecting errors soon after they are made, consistency checks guide the programmer towards the cause of the error. With consistency checks, the programmer can assume that most of the system is ok and its integrity preserved. Consistency checks can be implemented through assertion statements, check routines during data input and output, and through program state checks before prompting the user for input. If a function has an inverse such as sin/arcsine then function composition allow a quick consistency check of both functions. Checking can be reduced but should never be eliminated for production programs; especially program state checks. Consistency tests can be performed early in program development using requirements specification and redundant syntax. (cbb 5/80)
Subtopic: importance of checks up

Quote: no independent checks of Therac-25 malfunctioning; only patient reactions [»leveNG7_1993]
Quote: integrity constraints checked automatically, no voluntary action; concern of the community of users [»coddEF_1990]
Quote: self-checks identified errors missed by N-version coding and consistently found errors (if at all); since examined internal states [»leveNG4_1990]
Quote: consistency checkers lead to significant improvement in software error detection; e.g. type checking, range checks, and hardware initialization checks [»boehBW_1976]
Quote: consistency checks were best, followed by robustness checks (range check) and self-containedness (initialization) [»boehBW_1976]
Quote: telephone control programs are more than half audit code for automatic recovery from unintended states; masks software and hardware errors [»grieD_1981]
Quote: keeping two related, but different sets of data is asking for trouble; sooner or later someone will get them out of sync [»koenA12_1995]
Quote: write interface assumptions in prose; errors seldom occurred in both assumptions and programming constructs [»britKH3_1981]
Quote: PREfix and PREfast found 1/8 of the bugs fixed in Windows Server 2003 [»laruJR5_2004]

Subtopic: representation invariant up

Quote: the representation invariant of an abstract type defines its valid representations as the values of a data structure [»guttJV_2002]

Subtopic: SAT solver up

Quote: a formal framework for discovering inconsistency errors with a boolean SAT solver; e.g., 600 null dereferences in Linux [»dillI6_2007]

Subtopic: independent validation up

Quote: as you write code, look for opportunities to validate your results [»maguS_1993]
Quote: stepping through a program and comparing the results to a check sheet is the quickest way to find errors [»turiA3_1951]
Quote: use an independent check of the result to detect incorrect switch settings and incorrect plugging [»compHU_1946]
Quote: check the New Jersey Machine Code toolkit by generating machine code and assembly code; match results with a trusted assembler and a disassembler [»ramsN5_1997]
Quote: demonstrate the validity of Babbage's analytical engine by calculating numerical constants by multiple methods [»babbC_1864, OK]
Quote: before running a sequence tape, manually simulate the computation on a degenerate case or initial point; compare intermediate and final results with the actual computation [»compHU_1946]
Quote: double check the finite state model by setting and getting the user ids [»chenH8_2002]
QuoteRef: cbb_1973 ;;2/27/74 inverse eg arcsine (sin()) makes debugging much easier

Subtopic: test your assumptions up

Quote: developers should document their assumptions and write tests for these assumptions; catch changing conditions or inapproriate reuse [»smaaB2_2006]

Subtopic: physical checks up

Quote: hardware failure modes are more limited than software failures, so hardware interlocks should still be used
Quote: check for mechanical and electrical failures frequently; no more than 20 minutes without checks [»compHU_1946]
Quote: for sequence tapes in the tape library, the starting tapes should check all switches, plugging, and functional units; otherwise, they just compute the initial values [»compHU_1946]
Quote: run programmed checks often to detect problems early, avoid disastrous results, and diagnosis problems [»turiA3_1951]

Subtopic: fixed point testing up

Quote: self-test of compiler by fixed points; compile the compiler, then recompile; the two results should be identical; also recompile the runtime library for each machine [»auslM6_1982]

Subtopic: self-repair up

Quote: self-repairing application by specifying the key data structure consistency constraints; automatically detect and repair violations to these constraints [»demsB10_2003]
Quote: self-repair by consistency constraints in disjunctive normal form; repair actions to restore basic propositions; picks the least perturbation and prevents cycles [»demsB10_2003]

Subtopic: class and structure invariants up

Quote: every class should include a method to test its representation invariant; use to test and stress test representation inheritance [»edwaSH2_1997]
Quote: check routines for class invariants are an invaluable help during debugging and class definition [»stroB_1991]
Quote: check routines for class invariants provide an alternative viewpoint of the class and its implementation
Quote: production code should include some of the check routines for class invariants
Quote: use iContract for design-by-contract; easy to use [»jazeJM7_2001]
Quote: consistency management model for PLEIADES; consistency condition at a set of points, enforcement and inconsistency management [»tarrP4_1998]
Quote: the TOPD tester/checker stops on a missing item; could report everything missing [»hendP9_1975]
Quote: nonsensical execution causes arbitrary damage; may not effect program behavior until much later [»stroRE1_1986]
Quote: a lot of debugging is knowing which structures are intact; i.e., a bug is the breaking of some structure [»cbb_1973, OK]
Quote: MicroTool performs immediate consistency checking across all items in the program database [»elshJL1_1991]
Quote: a secure system must start in a consistent and secure state; EROS periodically verifies a consistent, global checkpoint of the entire state of the machine; used for bootstrapping [»shapJS1_2002]

Subtopic: database constraints up

Quote: constraint enforcement may be too expensive; if so, associate with a block of operations; e.g., database transactions [»tarrP4_1998]
Quote: integrity constraints checked automatically, no voluntary action; concern of the community of users [»coddEF_1990]

Subtopic: bug detector up

Quote: bug detectors for thread correctness, performance issue, security violation, usage bug, dropped exception, null pointer, open stream, unchecked return, unconditional wait [»hoveD12_2004]

Subtopic: checksums up

Quote: check magnetic tracks by computing checksums of their contents and comparing with known good values [»turiA3_1951]

Subtopic: type as consistency up

Note: type may be temporarily inconsistent; at 'return', can guarantee anything about a type [»cbb_1990, OK]

Subtopic: run-time type checking up

Quote: run-time checks of actual types; unallocated, uninitialized, integral, real, and pointer; shows exact location of errors; 20x slower [»logiA4_2001]

Subtopic: stable metrics up

Quote: HeapMD detects anomalies in stable, degree-based metrics of the heap; found 31 new bugs in large, commercial applications; 2-3x slowdown; few false-positives; call-stack log [»chilTM10_2006]

Subtopic: self-identifying data up

Quote: Babbage's analytical engine punched tables with x,y pairs; could verify that attendant brought the correct card [»babbC_1864, OK]
Quote: Babbage's engine would ring a bell for values of a transcendental; if given the wrong card, it would ring a louder bell [»compHU_1946]

Subtopic: unit testing up

Quote: use embedded test for self-testable components; evaluate quality with selective mutations [»jazeJM7_2001]
Quote: turn unit tests into parameterized, data-driven unit tests (PUT); generate inputs by symbolic execution and constraint solving [»tillN7_2006]

Subtopic: sampling up

Quote: use sampling to test for assertion failures across a large user base [»liblB6_2003]

Subtopic: copy-paste up

Quote: CP-Miner detects errors due to copy-paste; found 190,000 copy-paste segments and 49 errors in Linux [»liZ3_2006]

Subtopic: loop bound up

Quote: requiring a loop bound caught many design errors and was practical [»andeT_1985]

Subtopic: optimistic concurrency up

Quote: Bayou uses optimistic concurrency control; a write consists of an update set and a dependency check that calls a merge procedure on failure [»edwaWK10_1997]

Subtopic: proof checker up

Quote: certified evaluation via a proof checker for lists of facts, security rules, and derivations; 100 lines of code [»jimT5_2000]

Subtopic: units up

Quote: MicroTool supports physical units and checks for unit consistency [»elshJL1_1991]
Quote: syntactic redundancy reduces the number of possible errors by consistency testing [»cleaJC_1975]

Subtopic: avoid consistency testing up

Quote: prevent needing to rebuild a file system; ZFS has not needed FSCK in two years of deployment [»browD9_2007]

Subtopic: problems with consistency checking up

Quote: logic is not flexible enough for thinking because consistency is too strong a requirement [»minsM_1981]
Quote: wide individual differences in designing self-checks from requirements and code [»leveNG4_1990]
Quote: conditional trace and asserts bifurcates software; performance problems are found in production, but can only be understood in a development environment

Related Topics up

Group: debugging   (10 topics, 333 quotes)
Group: exception handling   (12 topics, 314 quotes)
Group: program proving   (10 topics, 311 quotes)
Group: type checking   (12 topics, 392 quotes)

Topic: automated tests of specifications and designs (12 items)
Topic: bugs (66 items)
Topic: compiler error checking (16 items)
Topic: constraints (35 items)
Topic: database agents (10 items)
Topic: database consistency and reliability (15 items)
Topic: debugging by usage rules (41 items)
Topic: debugging techniques (23 items)
Topic: defensive programming (22 items)
Topic: dependency analysis (34 items)
Topic: dynamic type checking (43 items)
Topic: error safe systems (76 items)
Topic: exceptions and undesired events (29 items)
Topic: error checking in robot programming (6 items)
Topic: file system reliability (26 items)
Topic: flavor analysis and typestates for supplementary type checking (68 items)
Topic: Goldstine and von Neumann consistency proof (6 items)
Topic: model checker (49 items)
Topic: path expression (14 items)
Topic: program proof via assertions (61 items)
Topic: program proving is infeasible (47 items)
Topic: proof-carrying code (7 items)
Topic: quality assurance (22 items)
Topic: range checking (20 items)
Topic: resourceful, redundant systems for reliability (38 items)
Topic: run-time assertions (25 items)
Topic: safety, liveness, and system properties (22 items)
Topic: self-identifying data structures (18 items)
Topic: testing by voting or N-version (10 items)
Topic: type-safe and secure languages
(43 items)

Updated barberCB 4/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.