贺敏，陈宏君

(1.国网电力科学研究院，南京 211106；2.南京南瑞继保电气有限公司)

图形化程序特征码的算法设计与应用

贺敏1，陈宏君2

(1.国网电力科学研究院，南京 211106；2.南京南瑞继保电气有限公司)

提出一种图形化页面程序特征码的提取算法。该算法根据图形化页面内符号间输入-输出数据流关系和数据类型信息，形成页面的中间信息文本。中间信息文本由该页面对外输入的输出变量名、变量类型，相关符号的输入、输出形参类型和参数设置值，输出变量的数据流调用表达式等关键内容拼接组成，基于中间信息文本计算形成CRC，作为页面的特征码。通过计算比较厂家内部修改页面、现场工程修改页面之间的特征码，给出页面程序修改是否一致的结果，该算法可准确甄别由于符号位置偏差、中间变量命名不同等原因导致的页面存储文件不同，但实际功能一致的情况。

图形化页面；特征码；中间信息文本；调用表达式

[5]利用载体字符计算出一系列伪随机代码，形成可及时纠正错误的可适应的文本数字水印。参考文献[6]针对短文本分类任务中文本表示存在的高维稀疏问题，提出基于自编码网络的短文本流形表示方法，可较好地描述短文本特征信息。尚未有参考文献阐述图形化页面特征码提取方案，常规的方法是比较图形化页面文件或产物文件。由于图形化绘制时，只要有一点点位置偏差，页面存储的文件必然不同，故没有可行性。而比较产物的方法，是将图形化页面形成代码，将代码编译形成HEX文件，比较HEX文件是否一致。然而，在绘制修改页面时，不能确保厂家内、现场新建、删除连接线的顺序前后一致。当中间连接线变量名是根据一定规则在绘制阶段自动命名时，连接线的命名由于绘制顺序不一致产生不同，故形成的连接变量名可能不同，导致形成的C代码产物或编译后的目标文件可能是不同的。而现场用户希望在编译前就能校验两者页面的一致性，并能排除中间变量命名、无关联关系的符号位置变化的无效差异，故通过比较产物的方式是行不通的。

本文设计了一种图形化页面程序特征码提取算法，通过比较两个页面的特征码，可快速得出页面修改是否一致的结论。

1 特征码算法设计

根据图形化页面的拓扑关系和数据类型信息，形成页面的中间信息文本。中间信息文本包括该页面对外输入的输出变量名、变量类型，相关符号的输入、输出变量类型和参数设置值，符号的数据流依赖调用关系等关键内容，基于中间信息文本计算形成CRC，作为页面的特征码，通过比较修改前后CRC1和CRC2是否相等，可判断页面是否一致,其中形成页面的中间信息文本是关键步骤。

1.1 中间信息文本形成方案

图1 图形化页面黑盒模型

如图1所示，将图形化页面视为1个黑盒子，对外可见部分为页面输入和页面输出，内部为符号块和连接线。

输入变量通过内部功能函数符号的数据流传递，最终连接到输出变量，其近似关系模型可用下述矩阵表示：

根据输出变量的数据流依赖关系，可形成若干输出变量的调用表达式，并且可以回溯到输入变量，顺次拼接表达式中的符号状态信息，就能记录该页面的断面数据，即经过拓扑连接处理后的中间信息文本。如图2所示，中间信息文本形成步骤如下：

① 读取图形化页面文件，包括输入符号、输出符号、功能函数符号、连接线等符号数据。

② 通过连接线记录的连接起始端符号ID、连接终止符号ID、连接起始变量名、连接终止变量名，形成输入输出的网状关系，每条连接线记录起始符号、终止符号、起始连接点、终止连接点的数据指针，每个符号的连接点记录与之相连接的连接线指针。

③ 根据连接线连接关系和指针双向记录结构，形成符号的输入-输出数据流依赖关系，根据数据流关系，形成有向无环的AOV等价网络，即页面可视为M个输入、N个输出的黑盒子，内部的功能函数网状连接形成。通过汇总输出变量的计算表达式和辅助信息，可得到等价中间信息文本。

④ 提取汇总页面对外的输入、输出符号，对输出变量按照名字进行降序排列(依次比较每位ASCII字符的数值，相同条件下短名字优先，例如ABC>ABCD)。

⑤ 设置循环变量i=1, 并置N=输出变量个数。

⑥ 依次取出排序后的输出变量，以输出变量Outi为终止点，前向回溯前驱符号的各个分支路径，按照广度优先算法完成前向回溯，直至回溯到输入变量或输入为0的变量。

⑦ 汇总各分支回溯路径中的符号名、符号的输入-输出名，逐级替换，得到输出变量的调用计算表达式和辅助设置信息。辅助设置信息包括分支路径中各符号的输入和输出变量类型、变量初始值、参数设置名和设置值，拼接形成字符文本段Si。

⑧i=i+1,i≤N,则重复步骤⑥到步骤⑧。

⑨ 将排序后的各个输出变量的文本段汇总形成页面的中间信息文本S=S1+S2+…+SN。

图2 中间信息文本形成方案

图3 图形化页面数据流示意图

以图3为例，介绍中间信息文本的具体内容。输出变量Out1前驱是XOR2, 则遍历L1时，可得到式(1)：

(1)

之后遍历XOR2的2个输入连接线L2，L3，可得到式(2)：

(2)

代入式(1)可得到式(3)：

Out1=XOR2(AND3.b1, OR3.b1)

(3)

再遍历 AND3的输入连接线L4、L5、L6，OR3的输入连接线L7、L8、L9，可得式(4)、式(5)：

(4)

(5)

代入到式(3)，可得到Out1的计算表达式为：

Out1=XOR2(AND3(In1,In2,In3),OR3(In4, In5,In6))

假设各个符号的变量类型为char、初始值为0，则辅助信息为：

In1.type=char,In2.type=char,In3.type=char Out1.type=char

AND3.a1.type=char,…XOR2.b1.type=char；

AND3.b1.init=0； OR3.b1.init=0；XOR2.b1.init=0；

最终输出变量的中间信息文本不包括中间连接线变量名，可排除内部连接线命名不同时误报不一致的情况。中间信息文本记录该变量名从输入变量到输出变量整个分支路径的关键信息，能有效检测出连接关系变化、调用顺序变化、功能函数变化、变量初始值变化、变量类型变化等差异。同时在拼接输出变量的信息文本时，对变量名进行排序处理，对于独立子网络的符号调整位置，不影响最终的中间信息文本。

1.2 AOV网广度优先遍历

在图2中，基于AOV网广度优先的遍历是个关键步骤。基于AOV网的处理方法，是把图形符号之间拓扑连接关系用有向图表示，在图中用顶点表示活动，用弧表示活动间的优先关系[7-8]。在AOV网中，不应该出现有向环，这意味着某项活动以自己为先决条件，程序的数据流存在闭环依赖，在遍历时会导致无限循环。而实际应用中图形化程序往往存在反馈闭环，即上个点的状态作为下个点的输入，这需要在遍历时进行检测，如果某个输出点最终遍历回溯到自身，则终止该输出点的前向遍历。

编程符号包括若干输入输出连接点，可以从输出点引出连接线到输入点，也可以从连接线中间引出连接线到输入点，从中间引出的连接线，在页面连接预处理阶段，将从逻辑上等价从源输出点连接。定义连接点类为CNode、符号基类为CShape、连接线类为CLine, 则三者关键数据结构定义如下：

class CNode { public:

CNode(CShape* parent); ～CNode();

QString name; //连接点名

QList lineList; //关联的连接线

};

class CShape { public:

CShape(CPage* page); virtual ～CShape();

QString id; //uuid唯一标识

QString type; //符号类型名

QList inList, outList; //输入、出点列表

};

class Cline { public:{

Cline(CPage* page); ～Cline();

QString id; //uuid唯一标识

QStringstartID, endID; //连接的起始、终点符号ID

QStringstartName, endName;//连接的输入输出点名字

CShape* pstartObj,pendObj; //连接对象指针

CNode* pstartNode, pendNode;//连接点指针

};

在读取页面数据后，建立符号ID和符号指针的hash表，并根据连接线记录的连接符号ID和连接点名字信息，查找相关符号和输入输出点，形成AOV网状的数据结构。基于输出连接点的前向回溯广度优先遍历的算法思想如下：

输入：

CNode* nd： 当前符号的输入点

QList& P: 页面中处理过的符号

QList& V: 此链路已经访问过的连接点

str: 中间信息文本

输出： 无

函数 makeNodeInfo(nd, P, V，str){

If(当前输入点nd已经存在于V) then 返回；

定义：

pline 为nd相连接的连接线

pstartnd 为 pline的起始连接点

pstartobj 为 pline的起始连接符号

If(pstartnd不为空) then str拼接pstartnd的信息;

If(psartobj不为空，并且不存在于P) then{

str拼接pstartobj的状态信息，包括输入、输出，参数等信息

pstartobj 添加到已经处理列表P

}

nd添加到V；

If(pstartobj不为空) then{

foreach(nd1, pstartobj->inList)

递归调用makeNodeInfo(nd1, P, V, str)

}

}

2 应用实例

2.1 验证修改前后特征码不一致

对表1中的内容进行修改能通过特征码判断出不一致。

表1 特征码不一致的修改

例如图4中，将逻辑运算输入AI_CLOSE_IND、CI_CLOSE_IND顺序调换，可验证出修改前后的特征码不一致。

图4 调换连接关系后判断修改不一致

2.2 验证修改前后特征码一致

对表2中的内容进行修改能通过特征码判断出一致。例如图5中，将独立网络PERMIT_CLOSE、INGATERING_235整体位置移动，验证出修改前后的特征码一致。

表2 特征码一致的修改

图5 独立网络调整位置判断修改一致

结 语

参考文献

[1] 邓秋娥,杜奇壮,卢娟.图形化编程在微机保护中的实现[J].继电器,2008,36(3):1-4.

[2] 韦恒,胡月.图形化编程技术在微机保护研发中的应用.电力科学与工程,2010,26(5):26-29.

[3] 陈宏君,刘克金,冯亚东,等.新一代保护测控装置配套工具软件设计与应用[J].电力系统自动化,2013,37(20):92-96.

[4] 刘克金,陈宏君,冯亚东,等.新一代控制保护系统图形化编程软件设计与实现[J].工业控制计算机,2014,27(10):82-87.

[5] 陈翔.基于文本特征的水印算法设计及关键技术研究[J].微型电脑应用,2013,29(8):1591-1599.

[6] 魏超,罗森林,张竞,等.自编码网络短文本流形表示方法[J].浙江大学学报,2015,49(9):62-64.

[7] 陈宏君,刘克金.嵌入式装置图形化程序代码生成技术[J].电脑编程技巧与维护,2015,8(4):95-97.

[8] Thomas H Cormen,Charles E Leiserson.Introduction to Algorithms[M].北京:机械工业出版社,2009.

贺敏(高级工程师)，研究方向为电力系统及其自动化软件；陈宏君(高级工程师)，研究方向为嵌入式软件平台开发。

Design and Application of Visual Graphical Program Feature Code

He Min1,Chen Hongjun2

(1.State Grid Electric Power Research Institute,Nanjing 211106,China;2.NR Electric Co.,Ltd.)

In the paper,a visualization page application signature extraction algorithm is proposed.The algorithm forms the middle information text of the page according to the inter symbol input and output data stream relation and data type information in the graph.The middle information text is composed of the key contents such as the page text among foreign input output variable name,variable type,the symbolic type of input and output parameters and parameter setting,the data flow call expression of output variables.The CRC calculation is formed based on the middle information text,which is used as the signature of the page.By comparing the calculation factory internal change page and the field engineering changes between the characteristics of the code,the result of whether the page program changes are consistent is given.The algorithm can accurately identify the symbol position deviation,the intermediate variable naming different causes such as the storage file,but the same function.

visual programming page;QR code;middle information text;call sentence

TP393

A

引 言

�士然

2016-08-24)

图形化编程已经在电力系统、工业控制等领域进行了大量的应用[1-4]。即将投运的直流输入控制保护、柔性输电保护工程，当遇到新的需求时，需要修改部分图形化页面程序。在这种情况下，首先是研发人员在厂家内修改相关程序，做完相关试验并经过审核确认后，将修改过的页面、修改步骤文档发给现场。技术支持人员从现场程序服务器签出需要修改的页面，根据修改说明步骤进行修改和编译，下载到装置。现场服务器是网络隔离的，不允许USB等端口操作，不允许直接用厂家修改的文件覆盖相关内容，这就存在研发修改的页面和现场修改的页面是否修改一致的问题，需要有校验的手段。