Pith. sign in

REVIEW 4 major objections 6 minor 31 references

High-Level Combined Deterministic and Pseudoexhuastive Test Generation for RISC Processors

T0 review · 4 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A test generator that uses only the instruction set out-scores gate-level ATPG on MiniMIPS.

desk verdict Real externally measured coverage win for an ISA-only SBST method, held back by a sketchy proof and a 100%-coverage claim that leans on deferred redundancy proofs. read the letter →

arxiv 1908.02986 v1 pith:XBFLABEY submitted 2019-08-08 cs.AR

Adeboye Stephen Oyeniran , Raimund Ubar , Maksim Jenihhin , Cemil Cem Gürsoy , Jaan Raik This is my paper · ORCID
classification cs.AR
keywords RISCprocessorshigh-levelfaultmodeltestgenerationdeterministicpseudo-exhaustivesoftware-basedself-teststuck-atfaultscontrolanddatapathtesting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes a software-based self-test generation method for RISC processors that works from the instruction set architecture alone, with no gate-level netlist or implementation details. The central idea is a new high-level control fault model: for each instruction, data operands are chosen so that every bit of that instruction's result can be forced to 1 and can be forced below the corresponding bit of every other instruction's result. The paper argues that a test satisfying these constraints for all non-redundant high-level faults also detects all non-redundant gate-level stuck-at faults in the control logic, and that this covers multiple stuck-at and bridging faults as well. On the MiniMIPS execute stage, the resulting test program reaches 99.02 percent gate-level stuck-at fault coverage, above the 97.73 percent of a commercial gate-level ATPG, with automated generation reported at about two orders of magnitude faster. A sympathetic reader would care because this is an implementation-independent route to the high fault coverage that safety standards demand.

What carries the argument

The load-bearing object is the high-level control fault model M(fi): the set of data operands Di such that for every bit k of result yi = fi(di), there is an operand making yi/k nonzero, and for every other function fj, an operand making yi/k < yj/k. These constraints are checked against an implementation-free equivalent disjunctive normal form (EDNF) of the ALU control part, an AND-OR multiplexer structure. The mechanism does two jobs: (1) it guarantees activation and observation of each control signal's stuck-at-0 and stuck-at-1 behavior through data comparisons, and (2) the strict inequality to every other function makes wrong-value overwrites observable, which is what extends coverage to multiple and bridging faults. The full test T* is the union of per-instruction tests; a fault table E records which bit-level inequalities are satisfied, and zero entries are treated as high-level redundancies to be manually removed.

What would settle it

Run an exhaustive or SAT-based search over m-bit operand pairs for each pair of instructions marked redundant in a fault table produced by this method; a single operand pair satisfying yi/k < yj/k for a zero entry would refute the redundancy treatment and, with it, Corollary 3's guarantee that the undetected gate-level faults are redundant. On MiniMIPS, an obvious candidate is the AND-versus-OR case where the paper asserts no data can make the result of an AND operation strictly less than the result of an OR operation.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: a high-level test T* generated to cover all non-redundant faults of the model M(fi), with data operands satisfying the two constraints (1) and (2), covers all gate-level non-redundant single stuck-at faults in the control part of the processor. The proof runs through an equivalent disjunctive normal form of the control logic: if every AND/OR path is exercised so that each output bit can be 0 and 1 in the required relative sense, no non-redundant stuck-at fault in the original optimized circuit can escape. Corollary 3 then states that if high-level redundancies are removed from the model, undetected gate-level stuck-at faults are redundant. The paper further claims (Corollary 4) that the same test covers multiple stuck-at and bridging faults between control lines, going beyond the single stuck-at fault class targeted by conventional gate-level ATPG. Experimentally, on the execute stage of MiniMIPS with 203,576 faults, the control-plus-pseudoexhaustive test reached 99.02 percent stuck-at fault coverage versus 97.73 percent for the commercial ATPG, with 166 stored patterns and 47 seconds of automated generation time.

Load-bearing premise

The 100 percent high-level coverage claim rests on treating every zero entry in the fault table as a redundant fault by manual inspection, while the paper does not prove those constraints unsatisfiable; if any removed constraint is actually satisfiable, the undetected gate-level faults would not be redundant and the reported coverage could be too high.

Editorial extensions

If this is right

  • Since generation needs only the instruction set, the method can test processor cores whose netlists are proprietary or unavailable, a case structural SBST cannot handle.
  • The same test data set serves both control and data path, so the deterministic control operands also contribute to data-path coverage at no extra memory cost.
  • The covered fault class includes multiple stuck-at faults and bridging faults between control lines, so the method targets a wider class than single-SAF gate-level ATPG.
  • On the MiniMIPS execute stage, the claimed 99.02 percent coverage exceeds the commercial gate-level ATPG's 97.73 percent with roughly two orders of magnitude less automated generation time.
  • If high-level redundancies are identified and removed, Corollary 3 turns the high-level test into a certificate that the remaining undetected gate-level stuck-at faults are redundant.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the constraint-satisfaction view suggests a SAT-based generator that automatically proves each zero entry unsatisfiable, which would remove the manual redundancy step and make the method fully automatic.
  • Beyond the paper, the same template-and-constraint structure could plausibly extend to decode stages, branch units, and register forwarding logic, since those are also control-dominated and instruction-visible; the paper does not demonstrate this.
  • Beyond the paper, the compact-template storage format (166 stored patterns) may have an interesting trade-off against execution time and code size on cache-resident self-test, which the paper does not quantify.
  • Beyond the paper, comparing 99.02 percent against an ATPG that targets only single stuck-at faults may understate the practical benefit if the true failure mechanisms include multiple and bridging faults, which this method claims to catch.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper proposes a high-level, implementation-independent SBST test program generation method for RISC processors. Instructions are partitioned into groups; for each group a test template runs the instruction under test with deterministic data operands for control-part testing (Definition 1, constraints (1)-(2)) and pseudo-exhaustive data operands for data-path testing. The paper states Theorem 1: a test covering all non-redundant high-level control faults also covers all gate-level non-redundant SAFs in the control part, via an EDNF equivalence result [27]; Corollaries 1-4 extend this to high-level redundancy and to multiple SAFs and bridging faults. Experiments on the MiniMIPS execute stage report 99.02% gate-level SAF coverage versus 97.73% for a commercial gate-level ATPG, with automated high-level test generation taking about 47 seconds versus 8 hours 27 minutes for ATPG. The 100% high-level coverage is obtained only after manually removing zero entries in Table 2 as redundant high-level faults, although the paper states that the proof of high-level fault redundancy is not part of its target.

Significance. If the theoretical mapping were rigorously established, the paper would be a valuable contribution to SBST: it offers an instruction-set-only test generation flow, reports externally measured gate-level SAF coverage on a synthesized MiniMIPS execute stage that exceeds a commercial ATPG, and does so with much lower automated generation time. The proposed fault model is also interesting in principle because constraints (1)-(2) target a broader fault class than single SAFs. The empirical result is plausible and deserves credit; however, the paper's central completeness claim is currently supported only by a proof sketch and by manually removing alleged redundant faults without a complete proof, so the theoretical contribution is not yet established.

major comments (4)
  1. [IV, Table 2 and Corollary 3] The paper's 100% high-level test coverage is obtained by manually deleting every zero entry of the high-level fault table E as 'high-level redundancies', yet Section IV states explicitly: 'The proof of high-level fault redundancy was not the target of the paper, and it needs special investigations.' Corollary 3 concludes that all remaining undetected gate-level SAFs are redundant, but this conclusion applies only if every deleted entry ei,j/k = 0 truly corresponds to an unsatisfiable constraint yi/k < yj/k. The paper provides partial truth-table arguments for a few ALU functions in Table 3, but not for all zero entries, including the single-bit entries e23 and e32 and the MOV/CMP rows. Without an exhaustive redundancy proof, or a SAT-based check of each deleted constraint, the claim of 100% high-level coverage is unsupported, and the experimental coverage figure cannot be interpreted as covering all non-redundant gate-level SAFs.
  2. [III, Theorem 1] The proof of Theorem 1 is a sketch: the first step asserts without demonstration that constraints (1)-(2) detect all SAFs in the DNF (3), and the second step invokes [27] to claim that a test detecting all non-redundant faults in an EDNF also detects all faults in the original optimized multi-level circuit, without stating the precise conditions of that equivalence or how they are met here. Since Theorem 1 is the basis for Corollaries 1-4 and for the paper's completeness claim, this gap is load-bearing. A rigorous proof, or a precise formal statement of the external theorem and its applicability, is needed.
  3. [III, Example 1] Example 1 calls faults c1 ≡ 1 and c2 ≡ 1 'redundant' because they disappear after minimizing the function in (4). Redundancy of a stuck-at fault, however, is a property of a specific gate-level implementation; a fault that is redundant in a minimized two-level form can be non-redundant in the original AND-OR DNF structure of Fig. 2. The example therefore does not demonstrate the claimed high-level redundancy, and it undermines the use of minimization to justify deleting zero entries from the fault table. This point needs to be corrected with an implementation-based redundancy argument or by changing the definition of high-level redundancy.
  4. [VI, Table 4] The timing comparison is not apples-to-apples. Table 4 lists 'Test generation time 47s' for the proposed method but also records 'Manually added PET data 8h 27m' for the better-coverage variant, while the text claims the high-level method is about two orders of magnitude faster than commercial gate-level ATPG. It is unclear whether the manual effort is included in the comparison and whether the ATPG runtime is reported under the same tool and machine conditions. The coverage advantage of 'Control + PET data' over 'Only control data' is partly due to manually generated data, so the cost of that manual step should be transparently reported.
minor comments (6)
  1. [Title] The title contains the typo 'Pseudoexhuastive'; it should read 'Pseudoexhaustive'.
  2. [Abstract] The abstract contains the typo 'partitioned nto groups'; it should be 'partitioned into groups'.
  3. [II, Definition 1] The formulas in Definition 1 are reproduced with garbled symbols; for example the displayed constraint (1) should clearly state that for every bit k there exists di with yi/k ≠ 0. Please ensure all equations are typeset correctly.
  4. [II, Definition 1] The model says the constant 0 in (1) and the relation '<' in (2) can be changed depending on technology. If the model is claimed to be implementation-independent, the dependence of the fault model on such technology-specific choices should be discussed explicitly.
  5. [IV, Algorithm 1] Algorithm 1 has a numbering error: the step numbering jumps from (5) to a second (5). Please renumber the steps.
  6. [VII, Conclusions] The conclusion states that coverage of bridging faults and multiple SAFs is 'based only on theoretical considerations' and defers experimental research to future work. This should be stated earlier in the paper, in the sections where Corollary 4 is proved, to avoid overstating the empirical contribution.

Circularity Check

0 steps flagged · score 2.0 of 10

No load-bearing circularity: the main SAF coverage numbers are externally benchmarked; the unproven redundancy removal is a correctness limitation, not a circular derivation.

full rationale

The paper's central experimental claim is the gate-level SAF coverage in Table 4 (99.02% vs 97.73% ATPG), obtained by running a commercial fault simulator on a Synopsys-synthesized MiniMIPS execute netlist. That number is not derived from the high-level fault model, so it cannot reduce to the model's inputs by construction. Theorem 1 depends on the external EDNF equivalence result [27] (Armstrong 1966), not on the authors' own prior work. The self-citations [28,29] provide PET data for the data-path variant, but the 'only control data' variant already exceeds the ATPG baseline (98.70% > 97.73%), so those self-citations are not load-bearing for the main comparison. The most serious acknowledged limitation is in Section IV: 'The proof of high-level fault redundancy was not the target of the paper, and it needs special investigations,' while Section VI says 100% high-level coverage was obtained by 'manual removal of the high-level fault redundancies.' This makes Corollary 3's conclusion that undetected SAFs are redundant dependent on an unproven classification of Table 2 zeros. That is a correctness risk and a gap in the theoretical claim, but it is not circularity: the gate-level SAF coverage is measured externally and is not statistically forced by the high-level fault table. Score 2 reflects the presence of minor self-citations and the definitional flavor of the redundancy removal, without load-bearing circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on three unproved or semi-proved premises: the EDNF test-completeness theorem, the representability of ALU control as an AND-OR DNF, and the treatment of unsatisfiable constraints as redundant faults. Of these, the last is the most fragile and is explicitly deferred. No numerical constants are fitted to data, and no new physical or formal entities are introduced.

assumptions (3)
  • domain assumption A test detecting all non-redundant faults in an equivalent disjunctive normal form (EDNF) also detects all faults in the original multi-level combinational circuit [27].
    Invoked in Section II and in the proof of Theorem 1 to bridge high-level DNF test results to arbitrary optimized gate-level implementations. The paper does not prove this theorem.
  • domain assumption The control part of an ALU can be represented as an AND-OR EDNF with one AND block per instruction, p control signals, and one OR block, independent of implementation details.
    Section II and Fig. 2 introduce this 'implementation-free' representation. It ignores sequential and additional control complexity such as pipeline interlocking, flag generation, and forwarding.
  • ad hoc to paper Unsatisfiable entries in the high-level fault table correspond to redundant high-level faults and can be removed without losing test completeness.
    Section III Corollaries 2-3 and Section IV; the paper explicitly says the redundancy proof was not its target and needs special investigation. This is an asserted premise, not a fully demonstrated one.

how reviews work

0 comments
Cite this review

Pith. "Pith review of High-Level Combined Deterministic and Pseudoexhuastive Test Generation for RISC Processors." pith.science (2026). https://pith.science/paper/XBFLABEY

@misc{pith2026190802986,
  author       = {Pith},
  title        = {Pith review of: High-Level Combined Deterministic and Pseudoexhuastive Test Generation for RISC Processors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XBFLABEY}},
  note         = {Machine review of arXiv:1908.02986}
}
read the original abstract

Recent safety standards set stringent requirements for the target fault coverage in embedded microprocessors, with the objective to guarantee robustness and functional safety of the critical electronic systems. This motivates the need for improving the quality of test generation for microprocessors. A new high-level implementation-independent test generation method for RISC processors is proposed. The set of instructions of the processor is partitioned nto groups. For each group, a dedicated test template is created, to be used for generating two test programs, for testing the control and the data paths respectively. For testing the control part, a novel high-level control fault model is proposed. Using this model, a set of deterministic test data operands are generated for each instruction of the given group. The advantage of the high-level fault model is that it covers larger than SAF fault class including multiple fault coverage in the control part. For generating the data path test, pseudoexhaustive data operands are used. We investigated the feasibility of the approach and demonstrated high efficiency of the generated test programs for testing the execute module of the miniMIPS RISC processor.

Figures

Figures reproduced from arXiv: 1908.02986 by the authors.

Figure 1
Figure 1. Fig.1 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 3
Figure 3. Fig.3 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [27]

    On Finding a Nearly Minimal Set of Fault Detection Tests for Combinational Logic Nets

    D.B.Armstrong. On Finding a Nearly Minimal Set of Fault Detection Tests for Combinational Logic Nets. IEEE Trans. on Electronic Computers, v.EC-15, no.1,1966 pp.66-73

    work page 1966

  2. [1]

    Software-based self-testing methodology for processor cores

    L.Chen, S.Dey. Software-based self-testing methodology for processor cores. IEEE Trans. on CAD of IC and systems, vol.20, no.3, 2001, pp. 369 - 380

    work page 2001

  3. [2]

    Software based self-testing of embedded processors

    N.Kranitis, A.Paschalis, D.Gizopoulos, G.Xenoulis. Software based self-testing of embedded processors. IEEE Trans. on Comp., vol.54, no.4, 2005

    work page 2005

  4. [3]

    Development Flow for On-Line Core Self-Test of Automotive Microcontrollers

    P.Bernardi, R.Cantoro, S.De Luca, E.Sanchez, A.Sansonetti. Development Flow for On-Line Core Self-Test of Automotive Microcontrollers. IEEE Trans. on Comp., v.65, no.3, 2016, pp- 744-754

    work page 2016

  5. [4]

    IEEE Design Test of Computers, v.27, no.3, 2010

    M.Psarakis, D.Gizopoulos, E.Sanchez, M.S.Reorda Microprocessor software-based self-testing. IEEE Design Test of Computers, v.27, no.3, 2010

    work page 2010

  6. [5]

    On the in-field functional testing of decode units in pipelined risc processors

    P.Bernardi, R.Cantoro, L.Ciganda, E.Sanchez, M.S.Reorda, S.D.Luca, R.Meregalli, A.Sansonetti. On the in-field functional testing of decode units in pipelined risc processors. IEEE Int Symp. on Defect and Fault Tolerance in VLSI and Nanotechnology Systems. 2014, pp. 299–304

    work page 2014

  7. [6]

    A flexible framework for the automatic generation of SBST programs

    A.Riefert, R.Cantoro, M.Sauer, M.S.Reorda, B.Becker. A flexible framework for the automatic generation of SBST programs. IEEE Trans on VLSI Systems, vol.24, no.10, 2016, pp. 3055–3066

    work page 2016

  8. [7]

    Towards an automatic generation of diagnostic in-field sbst for processor components

    M.Schölzel, T.Koal, S.Rieder, H.T.Vierhaus. Towards an automatic generation of diagnostic in-field sbst for processor components. LATW, 2013

    work page 2013

Show all 31 references
  1. [8]

    S.Gurumurthy, S.Vasudevan, J.A. Abraham. Automatic generation of instruction sequences targeting hard-to-detect structural faults in a processor. IEEE International Test Conference, 2006

    2006

  2. [9]

    L.Lingappan, N. K. Jha. Satisfiability-based automatic test program generation and design for testability for microprocessors. IEEE Trans. on VLSI Systems, vol.15, no.5, pp. 518–530, 2007

    2007

  3. [10]

    Simulation-based functional test generation for embedded processors

    C.H.Wen, L.-C.Wang, K.-T.Cheng. Simulation-based functional test generation for embedded processors. IEEE Trans. on Comp., vol.55, no.11, 2006

    2006

  4. [11]

    Kranitis, A

    N. Kranitis, A. Paschalis, D. Gizopoulos, and G. Xenoulis. Software based self-testing of embedded processors. IEEE Trans. on Comp., vol.54, no.4, 2005

    2005

  5. [12]

    Software-based self testing with multiple-level abstractions for soft processor cores

    C.H.Chen, C.K.Wei, T.H.Lu, H.W.Gao. Software-based self testing with multiple-level abstractions for soft processor cores. IEEE Trans on VLSI Systems, vol.15, no.5, pp. 505–517, 2007

    2007

  6. [13]

    Native mode functional test generation for processors with applications to self test and design validation

    J.Shen, J.A.Abraham. Native mode functional test generation for processors with applications to self test and design validation. Int. Test Conference, 1998

    1998

  7. [14]

    Frits - a microprocessor functional bist method

    P.Parvathala, K.Maneparambil, W.Lindsay. Frits - a microprocessor functional bist method. International Test Conference, 2002, pp. 590–598

    2002

  8. [15]

    I.Bayraktaroglu, J.Hunt, D. Watkins. Cache resident functional microprocessor testing: Avoiding high speed io issues. IEEE Int. Test Conference, 2006

    2006

  9. [16]

    Automatic test program generation: a case study

    F.Corno, E.Sanchez, M.S.Reorda, G.Squillero. Automatic test program generation: a case study. IEEE Design Test of Computers, vol.21, no.2, 2004

    2004

  10. [17]

    Zamboni, N

    D.Changdao, M.Graziano,E.Sanchez, M.Sonza Reorda, M. Zamboni, N. Zhifan. On the functional test of the BTB logic in pipelined and superscalar processors. LATW, 2013

    2013

  11. [18]

    Sanchez and M

    E. Sanchez and M. S. Reorda. On the functional test of branch prediction units. IEEE Trans. on VLSI Systems, vol.23, no.9, 2015, pp. 1675–1688

    2015

  12. [19]

    S. D. Carlo, P. Prinetto, and A. Savino. Software-based self-test of setassociative cache memories. IEEE Trans. on Computers, vol.60, no.7, 2011, pp. 1030–1044

    2011

  13. [20]

    On the functional test of the cache coherency logic in multi-core systems

    J.Perez Acle, R.Cantoro, E.Sanchez, M.Sonza Reorda. On the functional test of the cache coherency logic in multi-core systems. LATS, 2015

    2015

  14. [21]

    Ravi, A.Raghunathan

    D.Gizopoulos, M.Psarakis, M.Hatzimihail, M.Maniatakos, A.Paschalis, S. Ravi, A.Raghunathan. Systematic software-based self-test for pipelined processors. IEEE Trans. on VLSI Systems, vol.16, no.11, 2008, pp.1441–1453

    2008

  15. [22]

    14th Int

    P.Bernardi, R.Cantoro, L.Ciganda, B.Du, E.Sanchez, M.S.Reorda, M.Grosso, O.Ballan On the functional test of the register forwarding and pipeline interlocking unit in pipelined processors. 14th Int. Workshop on Microprocessor Test and Verification, Dec 2013, pp. 52–57

    2013

  16. [23]

    Hierarchical Pattern Faults for Describing Logic Circuit Failure Mechanisms

    K.B.Keller. Hierarchical Pattern Faults for Describing Logic Circuit Failure Mechanisms. US Patent 5546408, Aug. 13, 1994

    1994

  17. [24]

    Fault Diagnosis in Combinational Circuits by Solving Boolean Differential Equations

    R.Ubar. Fault Diagnosis in Combinational Circuits by Solving Boolean Differential Equations. Automation and Remote Control, Vol.40, No 11, part 2, Nov. 1980, Plenum Publishing Corporation, USA, pp. 1693-1703

    1980

  18. [25]

    On the Properties of the Input Pattern Fault Model

    R.D.Blanton, J.P.Hayes. On the Properties of the Input Pattern Fault Model. ACM Trans. Des. Automat. Electron. Syst., Vol. 8, No. 1, pp. 108-124, Jan. 2003

    2003

  19. [26]

    Adaptive Debug and Diagnosis Without Fault Dictionaries

    S.Holst, H.-J.Wunderlich. Adaptive Debug and Diagnosis Without Fault Dictionaries. Proc. of 13th ETS, Verbania, Italy, May 2008, pp.199-204

    2008

  20. [28]

    High-Level Test Data Generation for Software Based Self-Test in Microprocessors

    A.S.Oyeniran, A.Jasnetski, A.Tsertov, R.Ubar. High-Level Test Data Generation for Software Based Self-Test in Microprocessors. 6th Mediterranean Conference on Embedded Computing (MECO 2017), 2017

    2017

  21. [29]

    Parallel Pseudo-Exhaustive Testing of Array Multipliers with Data-Controlled Segmentation

    A.S.Oyeniran, S.P.Azad, R.Ubar. Parallel Pseudo-Exhaustive Testing of Array Multipliers with Data-Controlled Segmentation. Int. Symp. on Circuits and Systems (ISCAS), 2018

    2018

  22. [30]

    MiniMIPS ISA

    OpenCores, “MiniMIPS ISA”

  23. [31]

    Rejuvenation of NBTI-Impacted Processors Using Evolutionary Generation of Assembler Programs,

    F. Pellerey et al., "Rejuvenation of NBTI-Impacted Processors Using Evolutionary Generation of Assembler Programs," 2016 IEEE 25th Asian Test Symposium (ATS), Hiroshima, 2016, pp. 304-309 ! !

    2016

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.