Undetectable Attacks on Boolean Networks

Shiyong Zhu; Jianquan Lu; Jinde Cao; Lin Lin; James Lam; Michael Ng; Shun Ichi Azuma

doi:10.1109/CDC49753.2023.10383321

Undetectable Attacks on Boolean Networks

Shiyong Zhu^*, Jianquan Lu, Jinde Cao, Lin Lin, James Lam, Michael Ng, Shun Ichi Azuma

^*Corresponding author for this work

Department of Mathematics

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

2 Citations (Scopus)

Abstract

In this paper, driven by the ever-increasing cyber-security threats, we study the undetectable attack problems for Boolean networks (BNs), which model distributed systems with a limited capacity of storage and bandwidth of communication. Given a consistent monitor, undetectable attacks are formalized for BNs as those do not yield an output sequence out of the nominal output sequence set. By the graph-theoretic approach, undetectable attacks are characterized by a reachability problem of a directed cycle in the augmented transition graph. On the other hand, the algebraic approach also derives a necessary and sufficient criterion for undetectable attacks by testing the existence of the nonzero elements in the constructed matrix. While all these derived results are only computationally efficient for relatively small-size BNs. The detection of attack signals is indeed NP-hard. In other words, there is no polynomial-time algorithm to check the detectability of an attack signal or an attack node set unless NP=P.

Original language	English
Title of host publication	2023 62nd IEEE Conference on Decision and Control, CDC 2023
Publisher	IEEE
Pages	1698-1703
Number of pages	6
ISBN (Electronic)	9798350301243, 9798350301236
ISBN (Print)	9798350301250
DOIs	https://doi.org/10.1109/CDC49753.2023.10383321
Publication status	Published - Dec 2023
Event	62nd IEEE Conference on Decision and Control, CDC 2023 - , Singapore Duration: 13 Dec 2023 → 15 Dec 2023 https://ieeexplore.ieee.org/xpl/conhome/10383192/proceeding

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	62nd IEEE Conference on Decision and Control, CDC 2023
Country/Territory	Singapore
Period	13/12/23 → 15/12/23
Internet address	https://ieeexplore.ieee.org/xpl/conhome/10383192/proceeding

Scopus Subject Areas

Control and Systems Engineering
Modelling and Simulation
Control and Optimization

User-Defined Keywords

Algebraic state space representation
Boolean networks
NP-hardness
Security
Un-detectable attacks

Access to Document

10.1109/CDC49753.2023.10383321

Cite this

@inproceedings{f5d34548af5c4814affc2b976c76d013,

title = "Undetectable Attacks on Boolean Networks",

abstract = "In this paper, driven by the ever-increasing cyber-security threats, we study the undetectable attack problems for Boolean networks (BNs), which model distributed systems with a limited capacity of storage and bandwidth of communication. Given a consistent monitor, undetectable attacks are formalized for BNs as those do not yield an output sequence out of the nominal output sequence set. By the graph-theoretic approach, undetectable attacks are characterized by a reachability problem of a directed cycle in the augmented transition graph. On the other hand, the algebraic approach also derives a necessary and sufficient criterion for undetectable attacks by testing the existence of the nonzero elements in the constructed matrix. While all these derived results are only computationally efficient for relatively small-size BNs. The detection of attack signals is indeed NP-hard. In other words, there is no polynomial-time algorithm to check the detectability of an attack signal or an attack node set unless NP=P.",

keywords = "Algebraic state space representation, Boolean networks, NP-hardness, Security, Un-detectable attacks",

author = "Shiyong Zhu and Jianquan Lu and Jinde Cao and Lin Lin and James Lam and Michael Ng and Azuma, {Shun Ichi}",

note = "This work is supported in part by the National Natural Science Foundation of China under Grant Nos. 62273286 and 61833005, in part by the General Research Fund under Grant 17201820, in part by the Research Foundation of Yunnan Province No. 202105AF150011, and in part by the Grant-in-Aid for Transformative Research Areas (A) # 20H05969 (Molecular Cybernetics-Development of Minimal Artificial Brain by the Power of Chemistry) from the Ministry of Education, Culture, Sports, Science and Technology of Japan. Publisher Copyright: {\textcopyright} 2023 IEEE.; 62nd IEEE Conference on Decision and Control, CDC 2023 ; Conference date: 13-12-2023 Through 15-12-2023",

year = "2023",

month = dec,

doi = "10.1109/CDC49753.2023.10383321",

language = "English",

isbn = "9798350301250",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "IEEE",

pages = "1698--1703",

booktitle = "2023 62nd IEEE Conference on Decision and Control, CDC 2023",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/10383192/proceeding",

}

Zhu, S, Lu, J, Cao, J, Lin, L, Lam, J, Ng, M & Azuma, SI 2023, Undetectable Attacks on Boolean Networks. in 2023 62nd IEEE Conference on Decision and Control, CDC 2023. Proceedings of the IEEE Conference on Decision and Control, IEEE, pp. 1698-1703, 62nd IEEE Conference on Decision and Control, CDC 2023, Singapore, 13/12/23. https://doi.org/10.1109/CDC49753.2023.10383321

TY - GEN

T1 - Undetectable Attacks on Boolean Networks

AU - Zhu, Shiyong

AU - Lu, Jianquan

AU - Cao, Jinde

AU - Lin, Lin

AU - Lam, James

AU - Ng, Michael

AU - Azuma, Shun Ichi

N1 - This work is supported in part by the National Natural Science Foundation of China under Grant Nos. 62273286 and 61833005, in part by the General Research Fund under Grant 17201820, in part by the Research Foundation of Yunnan Province No. 202105AF150011, and in part by the Grant-in-Aid for Transformative Research Areas (A) # 20H05969 (Molecular Cybernetics-Development of Minimal Artificial Brain by the Power of Chemistry) from the Ministry of Education, Culture, Sports, Science and Technology of Japan. Publisher Copyright: © 2023 IEEE.

PY - 2023/12

Y1 - 2023/12

N2 - In this paper, driven by the ever-increasing cyber-security threats, we study the undetectable attack problems for Boolean networks (BNs), which model distributed systems with a limited capacity of storage and bandwidth of communication. Given a consistent monitor, undetectable attacks are formalized for BNs as those do not yield an output sequence out of the nominal output sequence set. By the graph-theoretic approach, undetectable attacks are characterized by a reachability problem of a directed cycle in the augmented transition graph. On the other hand, the algebraic approach also derives a necessary and sufficient criterion for undetectable attacks by testing the existence of the nonzero elements in the constructed matrix. While all these derived results are only computationally efficient for relatively small-size BNs. The detection of attack signals is indeed NP-hard. In other words, there is no polynomial-time algorithm to check the detectability of an attack signal or an attack node set unless NP=P.

AB - In this paper, driven by the ever-increasing cyber-security threats, we study the undetectable attack problems for Boolean networks (BNs), which model distributed systems with a limited capacity of storage and bandwidth of communication. Given a consistent monitor, undetectable attacks are formalized for BNs as those do not yield an output sequence out of the nominal output sequence set. By the graph-theoretic approach, undetectable attacks are characterized by a reachability problem of a directed cycle in the augmented transition graph. On the other hand, the algebraic approach also derives a necessary and sufficient criterion for undetectable attacks by testing the existence of the nonzero elements in the constructed matrix. While all these derived results are only computationally efficient for relatively small-size BNs. The detection of attack signals is indeed NP-hard. In other words, there is no polynomial-time algorithm to check the detectability of an attack signal or an attack node set unless NP=P.

KW - Algebraic state space representation

KW - Boolean networks

KW - NP-hardness

KW - Security

KW - Un-detectable attacks

UR - http://www.scopus.com/inward/record.url?scp=85184798935&partnerID=8YFLogxK

U2 - 10.1109/CDC49753.2023.10383321

DO - 10.1109/CDC49753.2023.10383321

M3 - Conference proceeding

AN - SCOPUS:85184798935

SN - 9798350301250

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 1698

EP - 1703

BT - 2023 62nd IEEE Conference on Decision and Control, CDC 2023

PB - IEEE

T2 - 62nd IEEE Conference on Decision and Control, CDC 2023

Y2 - 13 December 2023 through 15 December 2023

ER -

Undetectable Attacks on Boolean Networks

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this