, 杨文, Syed Naeem HAIDER清华大学 自动化系, 北京信息科学与技术国家研究中心, 智能与网络化系统研究中心, 北京 100084
收稿日期：2020-12-16
基金项目：国家重点研发计划项目（2017YFC0704100，2016YFB0901900）；国家自然科学基金项目（61425027）；高等学校学科创新引智计划资助项目（BP2018006）；北京信息科学与技术国家研究中心项目（BNR2019TD01009）；国家高速列车技术创新中心研发项目（CX/KJ-2020-0006）
作者简介：李学良(1988-), 男, 博士研究生
通讯作者：赵千川, 教授, E-mail: zhaoqc@tsinghua.edu.cn
摘要：可编程逻辑控制器（PLC）是工业控制领域中广泛使用的自动控制装置。由于PLC程序缺乏具有普适性的测试工具，开发人员往往只能采用人工方式排查代码错误，导致测试效率低下。工业用户亟需一种标准化PLC代码检测方法，自动完成PLC程序语法检测与分析。该文以IEC61131-3标准为基础，建立基于Backus-Naur范式（BNF）的指令表语法模型。基于该模型构造抽象语法树，进而设计出一种具有线性复杂度的PLC指令表代码语法检测算法。利用2段控制工程中的PLC指令表代码对所提出的算法与商用软件CODESYS Static Analysis进行对比测试，验证了所提算法的可用性。
关键词：可编程逻辑控制器(PLC)指令表(IL)静态分析IEC61131-3
A syntax analysis method of PLC instruction list program and its application in static testing
LI Xueliang, ZHAO Qianchuan
, YANG Wen, Syed Naeem HAIDERCenter for Intelligent and Networked Systems, Beijing National Research Center for Information Science and Technology, Department of Automation, Tsinghua University, Beijing 100084, China
Abstract: Programmable logic controllers (PLC) are automatic controllers widely used for industrial control. Because PLC program testing is lack of general testing tools, developers can only manually check code syntax errors, which is inefficient. Thus, industrial users need a standardized PLC code testing method to automatically complete the PLC program syntax detection and analysis. This paper presents an instruction list syntax model based on the Backus-Naur form (BNF) and the IEC61131-3 standard for industrial users. A PLC code syntax fault detection algorithm with linear complexity is then built with an abstract syntax tree to automatically check the PLC code syntax. Compared wich the CODESYS Static Analysis, analysis of two industrial PLC programs demonstrates the usability of this PLC code static analysis method.
Key words: programmable logic controller (PLC)instruction list (IL)static analysisIEC61131-3
可编程逻辑控制器(programmable logic controller, PLC)是一种稳定便捷的控制装置。PLC将传统的继电器控制、计算机技术和通信技术相结合，具有控制功能灵活、性能可靠稳定等特点，广泛应用于各种控制任务中。
使用PLC进行控制，需要特定操作环境及自动化、电路、机械等专业知识。为实现控制目标，工业用户对PLC程序正确性有着严格要求，代码中不能存在语法以及语义上的错误[1]。由于缺乏具有普适性的代码测试工具，开发人员往往只能采用人工方式排查代码错误，导致测试效率低下[2-3]。在此背景下，工业用户亟需一种标准化PLC代码检测方法，自动完成PLC程序正确性检测与分析。由于检测问题整体复杂性过高，本文只关注PLC代码语法正确性的静态分析。静态分析指在不运行代码的前提下，通过检查程序中的元素与结构分析代码正确性。现有的静态分析方法主要包括[4-6]：1) 抽象语法树结构分析法是将代码按照某种方式层次化，生成分支结构，通过遍历这种层级结构找出存在问题位置的方法，目前PLC代码的静态分析主要采用此方法；2) 控制流分析是从代码中提取操作得到控制流图的方法；3) 数据流分析是着眼于数据的来源、去向以及对数据的操作，生成数据生命周期图并展开分析的方法；4) 指针分析是分析代码中指针行为的方法，通过指针分析代码对内存的操作行为来检测代码的正确性；5) 抽象解释法会生成与源程序相似的模拟程序，通过运行该模拟程序，检查程序的正确性。
现有PLC厂商的控制系统互不兼容，执行程序内部标准也各不相同，缺少通用的静态分析工具。同时，已有的分析检测工具多数为非开源工具，只针对特定厂商的PLC程序预定义了检测规则，无法根据工业用户的具体测试需求进行改变。PLC的静态测试分析工具目前存在通用性不足、开放程度低等问题[7]，导致PLC代码静态测试分析不得不使用人工检测的方式进行，测试效率低下。
可喜的是，经过学术界和工业界多年努力，针对PLC语言的标准描述——IEC61131-3标准[8]于2003年提出了第2版。该标准为PLC语言设计提供了标准化的概念与方法，使建立PLC代码静态测试分析通用方法成为可能。目前PLC静态分析市场占有率最高的测试工具——CODESYS Static Analysis能对部分主流厂家的代码进行分析[9]，为IEC标准代码提供了有限的分析支持，但该工具非开源，所有检测规则已经预先定义且无法改变，仍未完全解决PLC静态测试存在的问题[10-11]。
IEC标准提供5种PLC代码格式，其中梯形图和指令表在工程中最为常见。本文以指令表格式代码作为研究对象，主要原因是指令表代码能够直接被控制器接受，且梯形图能够通过算法转换为指令表代码[12]。本文首先分析IEC标准的表达规范，基于Backus-Naur范式(BNF)建立模型，形式化地描述该标准的全部语法规则。然后，基于建立的模型，通过将双向链表转化为语法树的方法，提出一种检测语法错误的通用PLC代码分析算法。该算法从理论上提出一种判断程序是否符合IEC标准的依据，同时定位程序语法错误，支持PLC代码的自动化静态分析测试。最后，给出算法实例验证，并与CODESYS Static Analysis进行运行效率对比。
1 基于BNF范式的指令表语法规则为检验PLC代码语法是否符合IEC标准，需要对IEC标准指令表语法规则进行形式化描述。由IEC61131-3标准文本[13]可知，指令表代码包含程序组织单元和指令两部分。程序组织单元起到声明的作用，用于识别程序段的类型。IEC标准中合法的程序组织单元如表 1所示[13]。
表 1 指令表程序组织单元[13]
| 声明类型 | 程序结构元素声明 |
| 数据类型段声明 | TYPE; END_TYPE |
| 变量段声明 | VAR/VAR_INPUT/VAR_OUTPUT/VAR_ IN_OUTPUT/VAR_GLOBAL/VAR_TEMP/ VAR_EXTERNAL/VAR_ACCESS/VAR_CONFIG; END_VAR |
| 函数段声明 | FUNCTION; END_FUNCTION |
| 功能块段声明 | FUNCTION_BLOCK; END_FUNCTION_ BLOCK |
| 程序段声明 | PROGRAM; END_PROGRAM |
表选项
指令部分起到实现程序功能的作用，用于定义对变量执行的操作。IEC标准合法的指令代码具有以下格式：
| $\begin{array}{*{20}{c}}{标号:操作符/函数}&操作数&注释\end{array}$ |
表 2 IEC标准指令操作符[13]
| 指令类型 | 包含指令 | 备注 |
| 数据存储类 | LD、LDN | 需要带有一个任意操作数 |
| 输出类 | ST、STN | 需要带有一个任意操作数 |
| 置位与复位 | S、R | 需要带有一个BOOL型操作数 |
| 逻辑运算类 | AND、ANDN、OR、ORN、XOR、XORN、NOT | 需要带有一个任意操作数 |
| 算术运算类 | ADD、SUB、MUL、DIV、MOD | 需要带有一个任意操作数 |
| 比较运算类 | GT、GE、EQ、NE、LE、LT | 需要带有一个任意操作数 |
| 跳转与返回 | JMP、JMPC、JMPCN、RET、RETC、RETCN | JMP需要带有LABEL标号 |
| 调用 | CAL、CALC、CALCN | 需要带有一个函数名操作数 |
| 括号指令 | (, ) | 左括号一般和其他指令组合使用 |
| 注释 | (*、*) | 标识符内文字不会被检测执行，不允许嵌套 |
表选项
BNF范式作为语法设计中最常见的定义方式，编写简易，可读性强，不易产生歧义，是描述文本语法规则的良好形式。根据表 1和2，本文基于IEC标准设计了BNF范式的指令表语法规则，如图 1所示。由于语法规则条目较多，本文按规则性质将其划分为6类。图 1规则中的所有双引号内字符串均为关键字，不能用于变量定义。
 |
| 图 1 基于BNF范式的指令表语法规则 |
| 图选项 |
由图 1定义的语法规则可知，所有符合IEC标准语法规则的语法长度(规则中包含关键字与元素数量的最大值)均不超过6，这为检测算法的设计提供了便利。
2 基于语法规则的检测算法设计为实现语法自动检测，以节1构建的BNF范式为基础，本文提出一种依靠双向链表进行代码检测的算法。算法包括“代码分解”与“语法树形成”两个步骤。算法流程概要描述如下：1) “代码分解”步骤以PLC指令表代码作为输入，以空格与回车作为切割点，将代码分解成若干字符串，每个字符串作为一个对象进行处理，称为一个节点，生成图 2节点类定义的节点，每个节点的“类型”属性初始化为空。节点之间依照代码自上而下的扫描顺序首尾相连，形成一条节点具有左右相邻关系的双向主链表。2) “语法树形成”步骤以主链表为基础，从主链表头节点开始，依次检测链表中所有节点，通过对满足语法规则(由图 1定义)的节点组合进行拆解，形成语法树的新分支，同时根据节点组合满足的语法规则确定各节点的类型。代码不存在语法错误时，主链表会剩下唯一节点，并构成一棵完整的语法树。若存在不符合规则的代码时，主链表会剩余多个节点，每个节点对应的代码段均无法匹配语法规则。
 |
| 图 2 双向链表节点类定义 |
| 图选项 |
算法的具体描述如下：
1) “代码分解”步骤根据表 1和2将程序代码切割转化为节点，作为生成语法树的基础。这里采用C++格式定义节点的结构类以及相关操作函数，如图 2所示。“代码分解”步骤采用C++伪代码来表述，如图 3所示。图 4为该步骤的流程图。
 |
| 图 3 “代码分解”步骤的伪代码 |
| 图选项 |
 |
| 图 4 “代码分解”步骤的运行流程图 |
| 图选项 |
2) “语法树形成”步骤中，根据图 1的语法规则，对输入的双向链表中的每个节点及其左节点组合进行规则匹配。将满足语法规则的节点组合从主链拆出，在拆出位置处构建新的主链节点，令拆出的节点组合作为子链与其连接。在不断拆解与增添的过程中，直线双向链表转化为多层树状链表。“语法树形成”步骤如图 5所示，运行流程如图 6所示。该步骤的循环次数与语法规则的最大语法长度相关，假设所有被分解出的n个节点或其接邻组合都不满足任一语法规则，检测的时间复杂度为O(6!n)，为线性复杂度。
 |
| 图 5 “语法树形成”步骤的伪代码 |
| 图选项 |
 |
| 图 6 “语法树形成”步骤的运行流程图 |
| 图选项 |
3 算法示例本节通过分析符合IEC标准的浙大中控PLC指令表代码示例，说明本文所提算法的运行流程。图 7是一段用于读取压差传感器信号的代码。
 |
| 图 7 一段读取压差传感器信号的PLC指令表代码 |
| 图选项 |
执行图 3给出的“代码分解”步骤，得到图 7所示的代码的双向主链表，链表由17个节点构成。图 8给出了各节点的属性以及各节点在链表中的相对位置，1号节点为头节点，17号节点为尾节点。
 |
| 图 8 图 7示例代码的双向链表及节点属性 |
| 图选项 |
“语法树形成”步骤以图 8描述的双向链表作为输入。具体过程如下：
1)“分析指针”指向链表中的“节点1”，检验其不为空，使用NodeCheck函数检测“节点1”，语法库中不存在以关键字“FUNCTION_BLOCK”起始、同时长度为1的任一语法规则。此时分析指针所指“节点1”的左节点为空，分析指针移向“节点1”的右节点即“节点2”。
2) 对“节点2”使用NodeCheck函数检测，其不满足长度为1的任一语法规则。“节点2”存在左节点，因此使用NodeCheck函数以长度2进行检测，2个节点的类型检测不满足任一长度为2的语法规则。“节点1”左节点为空，分析指针移向“节点2”的右节点。
3) 不断重复对节点的检测，直至“分析指针”向后推移至“节点7”，此时NodeCheck函数检测到“节点7”及其左侧的3个节点满足语法长度为4的规则：〈VarDef〉: : =〈NAME〉“: ”〈ValueType〉“; ”，则将“节点4—7”从原链中取出，创建新的“节点A”，类型为语法左端的“VarDef”，内容为空，所在行为4个节点中最左端节点相同的第3行，左右节点分别为“节点3”和“节点8”，分别设定其指针，子节点指针指向“节点4”。改变过程如图 9所示。链表变化后，分析指针指向“节点A”。
 |
| 图 9 图 7示例代码主链拆解图示 |
| 图选项 |
4) 以“节点A”为检测节点，重复执行步骤1)—3)。在若干循环之后，双向链表最终会变为图 10的形式。算法执行完毕，双向链表上存在一个类型为“MainProgram”的“节点J”。算法结束。
 |
| 图 10 图 7示例代码的语法树及生成的新节点属性 |
| 图选项 |
算法完成后，由于双向链表只剩下类型为“MainProgram”的唯一节点，由此判断该代码语法正确。
下面给出本文算法对存在语法错误代码的检测示例。PLC指令表代码在IEC标准语法规则下的常见语法错误有以下几种[14-15]：代码框架不完整、声明缺失、组合指令部分缺失、指令操作数误用/缺失、跳转目标缺失等。假设程序中漏写了图 7代码的第5行“END_VAR”。在此情况下，算法给出的语法分析结果如图 11所示，输出的语法树主链上存在多个节点，由此判断代码存在语法错误。形成的新节点的“ErrorLine”属性指明代码无法匹配语法规则的行数。此例中算法停止后主链上形成的新节点的“ErrorLine”值为“3、5、6”，根据这些数据，编程人员能够定位错误，作出针对性的检查修改。
 |
| 图 11 图 7缺失第5行时的语法树及生成的新节点属性 |
| 图选项 |
4 工程案例测试本节分别使用本文提出的算法和CODESYS Static Analysis v3.2.0.0静态分析工具，在同一台个人计算机(CPU: Intel Core i5-8250U 1.60 GHz；内存: 4 GB)针对2段控制工程中的PLC指令表代码进行对比测试。根据文[8]的测试方法，在一段多机组中央空调控制程序中设置5个错误，在另一段飞行器姿态模拟控制程序中设置13个错误，这些错误均会使代码在写入后无法被PLC正确执行。测试结果如表 3所示。
表 3 两种算法的语法检测效果对比分析
| 算法 | 项目名称 | 代码行数 | 运行时间/ms | 定位错误行数 | 覆盖设置错误数量 |
| 本文算法 | 多机组中央空调控制程序 | 975 | 1 709 | 12 | 5 |
| 飞行器姿态模拟控制程序 | 1 767 | 13 158 | 73 | 13 | |
| CODESYS | 多机组中央空调控制程序 | 975 | 2 300 | 12 | 5 |
| 飞行器姿态模拟控制程序 | 1 767 | 19 700 | 60 | 12 |
表选项
表 3中：“定位错误行数”指算法检测出无法匹配语法规则的代码行数；“覆盖设置错误数量”指检测完毕后，确定的错误位置中存在已设置错误的数量。可以看出，两种检测方法均能较完整地检测出代码中存在的语法错误，但CODESYS分析结果忽略了1处可能由于分支使用不当导致的语法错误；本文提出的方法运行时间更短。
5 总结与展望在PLC代码分析领域，语法正确性检验是其他静态分析的基础。本文从工业用户的实际需求出发，通过对静态分析研究进展以及代码检验需求进行分析，针对IEC 61131-3标准中的指令表代码，提出一种基于BNF范式的语法检测算法，并通过实际对比运行测试，验证了所提算法的可用性。
本文提出的算法虽然能够辅助工业用户确定PLC代码中语法错误的位置，但排除语法错误仍需要程序员根据程序功能进行修改。
本文提出的BNF范式语法规则根据IEC标准进行构建，对PLC语言具有一定通用性。事实上，对于在IEC标准之外拥有独立功能指令的PLC语言，只需对本文提出的语法规则的关键字字典作出替换，即可利用本文算法对其他PLC语言进行代码语法分析。同时，本文算法在完成代码分析后形成的语法树，可以作为进一步开展代码结构分析、变量关联性分析、路径分析等工作的基础。
参考文献
| [1] | 赵千川, 王达, 薛文轩. PLC程序测试与验证的研究进展[J]. 清华大学学报(自然科学版), 2011, 51(11): 1617-1623. ZHAO Q C, WANG D, XUE W X. Testing and validation of programmable logic controller programs[J]. Journal of Tsinghua University (Science and Technology), 2011, 51(11): 1617-1623. (in Chinese) |
| [2] | 徐啸天. 一种PLC程序静态缺陷检测工具的设计与实现[D]. 南京: 南京大学, 2017. XU X T. Design and implementation of a static bug detection tool for PLC program[D]. Nanjing: Nanjing University, 2017. (in Chinese) |
| [3] | 王达. 一类工业控制软件测试与验证的几个关键问题研究[D]. 北京: 清华大学, 2011. WANG D. Research on key issues of test and validation in some industrial control software[D]. Beijing: Tsinghua University, 2011. (in Chinese) |
| [4] | HUNG M Y, CHEN P S, HWANG Y S, et al. Support of probabilistic pointer analysis in the SSA form[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(12): 2366-2379. DOI:10.1109/TPDS.2012.73 |
| [5] | BOUGOUFFA S, DONG Q H, DIEHM S, et al. Technical debt indication in PLC code for automated production systems: Introducing a domain specific static code analysis tool[C]//Proceedings of the 3rd IFAC Conference on Embedded Systems, Computational Intelligence and Telematics in Control, CESCIT 2018. Faro, Portugal, 2018: 70-75. |
| [6] | International Electrotechnical Commission. Programmable controllers-part 3: Programming languages: IEC 61131-3[S]. Genève, Switzerland: International Electrotechnical Commission, 2003. |
| [7] | PR?HOFER H, ANGERER F, RAMLER R, et al. Static code analysis of IEC 61131-3 programs: Comprehensive tool support and experiences from large-scale industrial application[J]. IEEE Transactions on Industrial Informatics, 2017, 13(1): 37-47. DOI:10.1109/TII.2016.2604760 |
| [8] | HOFER F, RUSSO B. IEC 61131-3 software testing: A portable solution for native applications[J]. IEEE Transactions on Industrial Informatics, 2020, 16(6): 3942-3951. DOI:10.1109/TII.2019.2941584 |
| [9] | JAMRO M. POU-oriented unit testing of IEC 61131-3 control software[J]. IEEE Transactions on Industrial Informatics, 2015, 11(5): 1119-1129. DOI:10.1109/TII.2015.2469257 |
| [10] | 王炜新, 周凯, 毛飞龙. 基于AOV和广义表的梯形图转指令表的转换算法[J]. 清华大学学报(自然科学版), 2019, 59(12): 1039-1044. WANG W X, ZHOU K, MAO F L. Transformation algorithm from a ladder diagram to an instruction list based on AOV and Lists[J]. Journal of Tsinghua University (Science and Technology), 2019, 59(12): 1039-1044. (in Chinese) |
| [11] | 彭瑜, 何衍庆. IEC 61131-3编程语言及应用基础[M]. 北京: 机械工业出版社, 2009. PENG Y, HE Y Q. Fundamentals of IEC 61131-3 programming language and application[M]. Beijing: China Machine Press, 2009. (in Chinese) |
| [12] | GRIMMER A, ANGERER F, PR?HOFER H, et al. Supporting program analysis for non-mainstream languages: Experiences and lessons learned[C]//Proceedings of 2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering. Suita, Japan, 2016: 460-469. |
| [13] | 高传平, 谈利群, 宫云战. 基于抽象语法树的代码静态自动测试方法研究[J]. 北京化工大学学报, 2007, 34(S1): 25-29. GAO C P, TAN L Q, GONG Y Z. Research on the syntax tree-based method for static and automated code testing[J]. Journal of Beijing University of Chemical Technology, 2007, 34(S1): 25-29. (in Chinese) |
| [14] | BIALLAS S, FRIEDRICH N, SIMON H, et al. Automatic error cause localization of faulty PLC programs[C]//Proceedings of the 5th IFAC International Workshop on Dependable Control of Discrete Systems: DCDS 2015. Cancun, Mexico, 2015: 79-84. |
| [15] | DUSCHL K C, GRAM? D, OBERMEIER M, et al. Towards a taxonomy of errors in PLC programming[J]. Cognition, Technology & Work, 2015, 17(3): 417-430. |
