TSU Sites

Tomsk state university

Institute of Applied Mathematics and Computer Science

Information & Hardware Security


Research Group on logic circuits testing, easy testable design and recovering, Tomsk State University

We have about 10 researchers involved in developing methods of testing, easy testable design and recovering of modern high performance logical circuits. These methods are based on applying discrete mathematics to different types of graphs representing circuit behavior or sums of prime implicants (SoPs) derived from logical circuits by using satisfiability problem (SAT) solvers when the graphs are very huge. In our studies, we verify obtained results on bench-marks (real logical circuits) using free tools (CUDD, ABC, Minisat and others). Our research group is well-known among specialists in logic circuit design and test theory around the world.

Leading researchers:

  1. Anzhela Matrosova (1941) – Professor, Doctor of Engineering, full professor at the Department of Computer Security, Tomsk State University. He has published 1 book and about 250 papers, including 110 indexed by Scopus and Wеb of Science.
  2. Sergey Ostanin (1974) – Professor-assistant, candidate of Engineering, head of the Computer Security Department, Tomsk State University. He has published about 100 papers, including 23 indexed by Scopus and Wеb of Science.
  3. Valentina Andreeva (1977) – Professor-assistant, candidate of Engineering, professor-assistant at the Department of Computer Security, Tomsk State University. She has published 50 papers, including 15 indexed by Scopus and Wеb of Science.

 Our group is developing methods, algorithms and programs of high performance logic circuits testing also testing with low power consumption, we develop methods, algorithms and programs of synthesis of easy testable, self-checking and fault tolerance logical circuits, methods, algorithms and programs of masking logic circuit faults and Trojan circuits injections into the circuits.

Main skills, developed methods and results:

1) It is revealed that the logical circuit derived from a ROBDD by covering internal nodes with Invert-AND-OR sub-circuits is fully delay testable and have rather short and simple  test detecting all multiple stuck-at faults on gate nodes of the circuit. The length of test is not more 4N, here N is the number of the ROBDD internal nodes. The suggested approach in comparison with methods developed by other authors does not demand additional inputs
2) The method of synthesis of full delay testable sequential circuits is developed. Obtained circuits are derived from composition of shared ROBDDs and monotonous irredundant sums of products (ISoPs). It is shown that the combinational parts of sequential circuits at the same time have rather simple tests for all multiple stuck-at faults at their gate nodes.
3) A method of deriving transfer sequence from the initial state of a sequential circuit into some internal state from the given set of internal states is developed. It is based on operations on ROBDDs obtained from combinational part fragments. If we have to only reveal a fact of existence of the sequence without finding the sequence itself we implement summing of cut ROBDDs depending only on internal variables of a sequential circuit.
4) A precise method of revealing, if the given path is false or not, for a sequential circuit under restriction on the length of a sequence delivering a test pair for non-robust path delay fault (PDF) of the path is suggested. It is reduced to multiplications and summations of ROBDDs extracted from fragments of the combinational part of a sequential circuit. As we know, there is no precise  methods for sequential circuits anywhere. Detecting false paths allows increasing speed of circuit operation.
5) A method of deriving all test patterns v2 from test pairs (v1, v2) for rising ( falling) transition of the given path is developed. It is reduced to operations on ROBDDs originated by fragments of a combinational circuit (the combinational part of a sequential circuit). Having got all test patterns v2 we may execute delay faults testing in sequential circuits without additional overhead.
6) A method of finding all test pairs of adjacent Boolean vectors for robust testable PDFs (both for rising and falling transitions of the path) is developed. All test pairs are compactly represented by the ROBDD. Having got all test pairs it is possible to get test sequences with low power consumption.
7) A method of deriving test sequence that detects robust testable PDFs of the given set of paths is suggested. It provides low power consumption during testing and based on operations on ROBDDs.
8) Methods of masking faults and ROBDD injections based on applying incompletely specified Boolean functions of circuit nodes obtained from the given circuit are developed. These methods are oriented to engineering change ordering (ECO) technologies and are founded on applying operations on ROBDDs derived from fragments of combinational circuits (combinational pars of sequential circuits).
9) Methods of self-checking and fault tolerance circuit synthesis for delay faults are developed. They are oriented to cut overhead.
We are going to wider above mentioned approaches to more complicated circuits using SAT solvers in combination with operations on ROBDDs. Some results in this direction we have already got.

Projects implemented by the group:

  1. Russian Science Foundation, N 14-19-00218. “Testing and test-fit design of high-performance logic circuits”, 2014-2018.
  2. State task of the Ministry of Education and Science of Russia “Research and development of probabilistic, statistical and logical methods and means of assessing the quality of components of telecommunication systems”, 2014-2016.


Recent significant papers:

  1. Matrosova A.Y., Mitrofanov E.V., Akhynova D.I. Mathematical processing of physics experimental data: Providing reliability of physical systems: Fully delay testable logical circuit design with compact representation of all pdf test pairs //Russian Physics Journal. 2015. Vol. 58, № 9. P. 1321-1330.
  2. Matrosova A.Yu., Lipskii V.B. Properties of pairs of test vectors detecting path delay faults in high performance VLSI logical circuits //Automation and Remote Control. 2015. Vol. 76, № 4. P. 658-667.
  3. Matrosova A.Yu., Kirienko I.E., Tomkov V.V., Miryutov A.A. Reliability of Physical Systems: Detection of Malicious Subcircuits (Trojan Circuits) in Sequential Circuits //Russian Physics Journal. 2016. Vol. 59, № 8. P. 1281-1288.
  4. Matrosova A.Yu., S.A. Ostanin, I.E. Kirienko, E.A. Nikolaeva. A fault-tolerant sequential circuit design for stuck-at faults and path delay faults //Вестн. Том. гос. ун-та. УВТиИ. 2017. № 41. P. 61-68.
  5. Matrosova A., Mitrofanov Е., Shax T. Simplification of fully delay testable combinational circuits and finding of PDF test pairs //Вестн. Том. гос. ун-та. УВТиИ. 2017. № 39. С. 85-93.
  6. Matrosova A.Y., Mitrofanov E.V., Ostanin S.A., Butorina N.B., Pakhomova E.G., Shulga S.A. Detection and masking of trojan circuits in sequential logic //Вестн. Том. гос. ун-та. УВТиИ. 2018. № 42. P. 89-99.
  7. Matrosova A.Y., Andreeva V.V., Chernyshov S.V., Rozhkova S.V., Kudin D.V. Finding false paths in sequential circuits //Russian Physics Journal. 2018. Vol. 60, № 10. P. 1837-1844.
  8. Matrosova A.Yu., Andreeva V.V., Nikolaeva E.A. Finding Test Pairs for PDFs in Logic Circuits Based on Using Operations on ROBDDs //Russian Physics Journal. 2018. Vol. 61, № 5. P. 994-999.
  9. Shah T., Matrosova A., Fujita M., Singh V. Multiple stuck-at fault testability analysis of ROBDD based combinational circuit design //Journal of Electronic Testing. 2018. Vol. 34, № 1. P. 53-65.
  10. Matrosova A.Yu., Mitrofanov E.V., Shah T. Simplification of Fully Delay Testable Combinational Circuits //Proceedings of the 21st IEEE International On-Line Testing Symposium. Danvers, Massachusetts, 2015. P. 44-45.
  11. Matrosova A., Ostanin S., Kirienko I., Nikolaeva E. A Fault-tolerant Sequential Circuit Design for SAFs and PDFs Soft Errors //2016 IEEE 22nd International Symposium on On-Line Testing and Robust System Design (IOLTS). Sant Feliu de Guixols, Spain, 2016. P. 1-2. URL:: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7604655&isnumber=7604654.
  12. Matrosova A., Ostanin S., Andreeva V. Patching circuit design based on reserved CLBs //Proceedings of 2016 IEEE International Conference on Automation, Quality and Testing, Robotics (AQTR). Romania: IEEE Computer Society, 2016. P. 49-54.
  13. Shah T, Matrosova A., Singh V. Test Pattern Generation to Detect Multiple Faults in ROBDD based Combinational Circuits //2017 IEEE 23rd International Symposium on On-Line Testing and Robust System Design (IOLTS). Thessaloniki, Greece: IEEE Computer Society, 2017. P. 211-212. URL: http://rpsonline.com.sg/rps2prod/FEDfRo2017/e-Proceedings/IOLTS2017/html/107.xml.
  14. Shah T, Matrosova A., Binod K., Masahiro F., Singh V. Testing multiple stuck-at faults of ROBDD based combinational circuit design //2017, 18th IEEE Latin American Test Symposium (LATS) [Electronic resource], 13-15 march 2017. [Bogota]: IEEE Computer Society, 2017. P. 1-6. URL: http://ieeexplore.ieee.org.
  15. Matrosova A., Mitrofanov Е., Ostanin S., Kirienko I. Trojan Circuits Preventing and Masking in Sequential Circuits //2017 IEEE 23rd International Symposium on On-Line Testing and Robust System Design (IOLTS). Thessaloniki, Greece: IEEE Computer Society, 2017. P. 213-214. URL: http://rpsonline.com.sg/rps2prod/FEDfRo2017/e-Proceedings/IOLTS2017/html/108.xml.
  16. Matrosova A., Andreeva V., Tychinskiy V. Deriving Low Power Test Sequences Detecting Robust Testable PDFs //Proceedings of 2019 IEEE East-West Design & Test Symposium (EWDTS), 13-16 september 2019, Batumi. Kharkov: IEEE, 2019. P. 406-409.
  17. Matrosova A., Provkin V., Nikolaeva E. Masking Internal Node Faults and Trojan Circuits in Logical Circuits //Proceedings of 2019 IEEE East-West Design & Test Symposium (EWDTS), 13-16 september 2019, Batumi. Kharkov: IEEE, 2019. P. 416-419.
  18. Matrosova A., Ostanin S., Chernyshov S. Masking Robust Testable PDFs //Proceedings of 2019 IEEE East-West Design & Test Symposium (EWDTS), 13-16 september 2019, Batumi. Kharkov: IEEE, 2019. P. 420-423.
  19. Toral Shah, Anzhela Matrosova, Virendra Singh. PDF testability of a combinational circuit derived by covering ROBDD nodes using Invert-And-Or circuits //2015, 19th International Symposium on VLSI Design and Test (VDAT 2015) [Electronic resource] : proceeding,  26-29 june 2015. Ahmedabad: IEEE Computer Society, 2015. P. 1-2. URL: http://ieeexplore.ieee.org/document/7208130/.
  20. A. Matrosova, V. Andreeva, A. Melnikov. ROBDDs Application for Finding the Shortest Transfer Sequence of Sequential Circuit or Only Revealing Existence of this Sequence without Deriving the Sequence itself //Proceedings of IEEE East-West Design & Test Symposium (EWDTS’2016). Kharkov: IEEE Computer Society, 2016. P. 513-516.


SD-WAN Systems:

We explore Internet-based and cloud-based publicly available SD-WAN systems using well-known Shodan and Censys search engines and custom developed automation tools and show that most of the SD-WAN systems have known vulnerabilities related to outdated software and insecure configuration.

    We hold academic research in the field of automata cryptography and FPGA implementations of cryptosystems based on finite automata, database management systems for encrypted databases.

    1.  Trenkaev V.N. Reconfigurable Finite State Machines Based on Substitutions // Prikladnay Diskretnaya Matematika. Prilozhenie, 2019, Issue 12, pages 192–193 (in Russian)
    2. Glotov I., Ovsyannikov S., Trenkaev V. Computationally secure DBMS based on order-preserving encryption // Prikladnay Diskretnaya Matematika. Prilozhenie, 2014, Issue 7, pages 81– 82 (in Russian)
    3. Kovalev D., Trenkaev V. Zakrevskij's cipher FPGA implementation based on the formula-defined reconfigurable FSM // Prikladnay Diskretnaya Matematika. Prilozhenie, 2014, Issue 7, pages 142– 143 (in Russian)
    4. Trenkaev V.N. Zakrevskij's cipher based on reconfigurable FSM // Prikladnay Diskretnaya Matematika, 2010, Issue 3(9), pages 69–76 (in Russian)