基于XPath分解XML文档的完整性检查

1、基于xpath分解xml文档的完整性检查刘宝龙刘念，陈桦（西安工业大学 计算机科学与工程学院，中国，西女，710032）摘要：xml文档的分解在xml数据女全、文档发布中有着广泛的应川，xml文档在分解时需要考虑两个问题：首先，每一个分解的子文档应该是有意义的。其次，数据完整性机 制应能检查每一个子文档的完整性。本文利用xpath路径表达式实现xml数据的分解，并 提出建立一个xml数据完整性检查池来提供分解后的xml数据完整性检杳。利用xpath 表达式，在保持子文档有效性的同时易于实现xml文档的分解。利用建立的数据完整性检 杳池，用户对以检杳所得数据的完整性，而不需要和其他用户的协作。该

2、方法的提出为细粒 度安全坏境中对xml文档的保护及发布提供了新的思路，为xml应用奠定了女全基础。 关键词：xpath；完整性检杏池；dom-hash； dtd中图号：tp309.2文献标志码：axml文档分解在xml数据安全屮有着广泛的应川，比如：基于信任第三方文档的发布、 基于工作流的多重xml数字签名及加密等。文献中提岀了一种xml文档分解的方案。 该方案假定文档m可以被分解成一系列不交叉的更小的子文档，记为t = %w2，.,%， 其屮每一个叱仅包含一个独立的对象，并假定叱是一个顺序序列，因此整个文档可以看做 是这些子文档连接的结果，即：耐=呦11叫11ii叱”。尽管上述方法可以分解一

3、个xml文 档，但是该方案的一个主要缺陷是：假设每一个文档可以被分割成一系列的子文档，并且每 一个子文档是有效的。这是一个严格的假设，因为一个完整的有效的主题或许包含一个文档 的几个部分。保持这些子文档的完全有效性是不容易的。利用xml数据的结构，文献2采 川xpath路径集合t二仏心,口来分解一个文档m ,并生成一系列子文档 二仙,w2,其中右代表xpath表达式。通过xpath表达式,用户可以容易的获得一 个子文档叱o这个方案的主要优点是基于xpath分解的文档可以保证每个文档的完整含义。 收稿日期：2012-04-10作者简介：刘宝龙（1976），男，西安工业大学计算机科学与工程学院，博

4、士，主要从事xml 安全技术方血的研究。email: liu.bao.lonq 手机讯作者：刘宝龙 email: liu.bao.lonq然而，这个方案中存在两个明显的缺陷。首先，在文档分解过程屮，每一个子文档的完整性 检査依赖公式ilvr2 ii.ii h-这表明原始文档的每一个部分必须被完全的分派， 否则完整性检查将是不可行的。比如，假设一个文档由5个部分组成，实际应川屮只需要 对其中的3个部分进行处理。这样一来，其余2部分并没有被分派，按照公式 （"）（叩叫11.1也”）进行完整性检查时总会返回一个失败的完整性检查;其次,子文档 的完整性检查需要所有分

5、解结果在线协同检杳，这在实际应用中随着分解数目的增加是不现 实的。基于以上分析，本文利用xpath表达式來分解xml数据，并设计一个完整性检查池來 检查分解子文档的完整性。该方案的基木思路是对原xml数据进行最小单位的xpath分解, 并将分解的结果利用hash算法进行处理，采用自下而上的验证过程，用八利用完幣性检 査池中提供的对应路径的摘要值，可自行完成分派数据的完整性检査，不需要同其川户进行 协同检查，而m xml数据不需要全部被分解，可以离线完成完整性验证。该方法的提出为 细粒度安全环境屮对xml文档的保护奠定了基础，为xml数据安全起到了促进作川。1理论导引有多种方法来确保信息的完整性

6、，比如摘要值或者校验和机制。这两种方法都可以丿ij 來发现原始信息发生的改变。然而，摘要值关注恶意攻击，而校验和主要川于发现偶然的变 化。本文采用hash算法机制来确保数据的完整性。釆取hash算法机制作为检查数据完整 性方法的原因主要有两点【叽（1）校验和通常用于检测数据的偶然变化，校验和在受到恶意 攻击时提供的安全等级较低，因为它的数学结构使其更容易被破坏。crc系列就是一个例 子。（2）基于复杂数学模型的hash函数具有单向性和抗冲突性，因此它捉供的女全等级比 校验和要高。hash算法的定义如下：y = /z（m）（1）其中/?是一个hash算法，m是一个消息，y是hash算法产生的数字

7、摘要值。hash算 法有如下特征：（1 ） 输入的可以是任意人小的数据块。（2）产牛一个固定氏度的输出，并且它就叫做摘要值或者消息摘要o(3) 对于任意给定的摘要值y ,找到一个信息m使其满足公式h(m) = y是不可能的， 这里称为hash算法的单向性。(4) 给定一个消息m ,找到m hm'且/7(m) = /2(m')的情况是很困难的。(5) 找到任一满足公式hm ) = h(m )的信息对(m , m')是很闲难的。现今广泛应用的hash算法有md5以及sha系列 表1列出了常用hash算法的一些 参数及显现的hash冲突问题。表1常用hash算法table 1

8、 commonly used hash algorithmhash函数块大小(bits)输出(bits)冲突情况(复杂度)md5512128有(220.96)sha-0512160有(233.6)sha-1512160冇(251)sha-256512256无sha-5121024512无从表1屮可以看岀，md5、sha-0和sha1由于存在哈希冲突，所以不是用于产生摘要值的一个很好选择。尽管sha-256和sha-512的运算速度比md5、sha-0和sha-1慢,但是到目前为止还没有发现哈希冲突，所以可以女全使用。而且，nist (national institute of standard

9、s and technology)也推荐在应用中使用sha-256,基于这个事实，hash算法在应川中是可以确保女全性的。2数据完整性检查池 2.1检查池的生成为了更清楚地说明问题，在定义1中描述了 bertino给出的一个xml数据的抽象定义, 基于这个定义，随后介绍了数据完整性检査池的建立过程。定义x 个xml数据是一个4元组：二少,厂,，其中,(1) 分别代表元素和属性的集合。每一个vgv"对应一个属性值，每一个y w v-都有一个相关的数据值。(2) 厂是xml文档的根节点。(3) e(l vexve是边的集合。(4) 是边的标记函数。基于xpath路径表达式来进行xml数据

10、分解的方法相关文献屮描述较多，这里不再赘 述，木部分内容主耍关注于xml数据完整性检查过程。xml数据完整性检查池的慕木思路 来源于xml数据的树形结构。如果一个用户伉知道一个xml数据x。的根节点摘要值，那 么就可以证明对于出现在x。下的任意xml数据子树刃的完整性。这一过程为，用八可以 通过dom (document object model)子树st来产牛st的摘要值，通过给出st兄弟节点的摘 要值，就可以计算出其父节点的摘要值，以此类推，在知道其父节点的兄弟节点的摘要值, 用户可以计算出根节点的摘耍值。基丁单向hash算法的特征和摘要值的比较，就可以判定 子树“是否包含在xml数据这种

11、处理也可以川于证明一个子树刃是否包含在另一 个子树中。利川这个特性，可以检查一个子树或者节点的完整性，进而检查分解子文档的完 整性。针对xml数据的特点，定义2描述了计算一个dom子树摘要值的计算方法及过程。定义 2 dom-hashxml内容完整性应该保护元素名称、属性、元素的值及指令。把x。作为一个元素或者 子树，作为一个冲突避免的单向hash算法。dh(v)和x。结合起来是一个函数，并且对 于每一个v g v ：_ rr. . h(v.content) ii (v.attribute) ii (dh(v.child) ii ii dh(v.child11) if v is a verli

12、ce( 2 )dhv)= <h(vcontent) ii (v.altribute) if v is a leafnode公式2仅提供每一个元素或者部分xml数据的摘要值，其小，v.content eve , v.attributeev /?是一个冲突避免的单向 hash 算法，如 sha-512； v.child1 (i = 表 示节点v的第，个孩子；表示连接运算符。此定义基于连接的hash算法，也就是说首先 对元素的所有孩子进行连接操作，然后产牛一个摘要值。这样可以降低摘要值计算过程中虚 拟节点的数量，进而提高摘耍值的计算效率。给定一个 xml 数据 x。，对应 xml 数据的 dt

13、d (document type definition)其 xpath 路径数量为一个有限值，数据完整性检查池t在定义3中描述。定义3设xml数据完整性检査池为，？为一个四元组(r,p,c(p),dh(c(/;),其中:厂表示一个xml数据文档x,)根节点对应的摘要值； p是dtd中可能的xpath路径表达式； c(p)表示xpath路径表示卩所指向的数据内容； dh(c(p)是数据内容c(p)对应的摘要值。根据定义3小描述的xml数据完整性检查池，一个xml数据完整性检杳池r的产生过程如下所示：步骤1：根据与xml数据相关联的dtd中每一个可能的xpath路径表达式小=1,.)获取与该路径路

14、径所指向的数据内容c(p),将必及c(pj插入到检查池c步骤2：采用上文描述的dom-hash函数牛成对应数据内容的摘要值dh(c(pj),并 令叫=dh(c(pj)。步骤3：设“为xml数据中某一子树的根节点，其对应的摘要值为饥：hst =/?(/?(加)1*(® )11 1*(叫)，其中表示子树*包含的孩子节点或者子树数目; 按照自底向上递归的方式，可以计算出一个xml数据x。根节点对应的摘要值厂，将厂插入 t中。2.2利用检查池进行完整性验证假设xml文档x。对应的完整性检查池为八 川户请求检查的xpath路径为q,完整 性检查由以下儿个步骤组成。步骤1：把g与t中每一个路径条

15、目做对比。如果q与2中的条目相匹配，获取门对 应数据内容的摘要值dh(c(pj),令m = dh(c(pj)，转入步骤2。如果没有符合的条口与g 相匹配，那么表示x»中不存在这样的路径。?步骤2：用户采用dom-hash生成g对应的哈希值加，并检查m =m ,女保 加工加， 则表明q对应的数据内容非原始数据，否则表明该数据可信，为文档中的原始数据。如果用 户认为该结论不可信，则可转入步骤3进行扩展检查。步骤3：假设g是q对应的父节点路径，以步骤g为路径表达式重新开始步骤1。辙， 用户可以得到xml数据x。的根节点对应的摘要值厂，判断r如果不相等，则表明q对应的数据内容确非原始数据，如

16、果相等否则表明该数据可信。步骤3得到的是这是一个 令人信服的结果，因为整个xml数据的完整性已经检查过了。2.3应用实例图1给出了一个客户资料信息的xml文档，rh于需耍用户口己对相关数据进行认证， 因此，衣实际应川中首先需要对每个客八对应的资料信息述行提取，然厉发送给用户核对。 在操作过程中，采用xpath路径表达式生成子文档，然后在服务器上发布，这时客户需要 对验证发布数据的完整性。对应该实例文档，其dtd如图2所示。由图2中的dtd,系统可以产生该文档可能的所有xpath路径表达式。<?xml version=n1.0h?><paymentlist xmlns=nhtt

17、p://paymentn> <paymenthifo><name>john smith</name><creditcard limit=m5,000m currency=hgbph> <numbei>4019 2445 0277 5567</number> <issucr>hs bc</issucr><ex p i rat ion> 14/0 2</ex p irat io n> </creditcard></paymentinf

18、o><paymen(info><name>gary allen</name><creditcard limi匸”4.000“ currency=”gbp“> <numbei>3920 4453 1279 3566</number> <issucr>lloyds tsb</issucr><expiration>l 3/05</expiration></creditcard></paymentinfo></paymentlist>图1客户

19、资料xml文档<?xml version=n1.0h encoding=hutf-8h?><!element paymentlist (paymentinfo+)> <!attlist paymentlistxmlns cdata#fixed "/payment"> <!element paymentinfo (name, creditcard)> <!element number (#pcda1a)>v!elementnamc (#pcda1a)><!element

20、issuer 併 pcdata)><!element expiration (#pcdata)><!elem ent creditcard (number, issuer, expiraiion)> <!attlist creditcardcurrency cdata #fixed ”gbp”limit cdata #fixed ”5、000”>图2客户资料文档对应的dtd对于给出的应用实例及文档相关的dtd,数据完整性检查池的牛成过程及结果如下:表2 xml数据完整性检查池tabic 2 xml data integrity-checking poo

21、l编号xpath路径对应内容摘要值1/paymentlistlmbp.2/paymentlist/paymentinfo 142ry.3/paymentlist/paymentinfo 1 /namejohn smithdfgq.4/paymentlist/paymentinfb 1 /creditcarduto9.5/paymen tlist/paymentinfb 1 /creditcard/limit5000puty.6/paymen tlist/paymentinfb 1 /creditcard/currencygbplk69.7/paymcntlist/paynicntinfo 1

22、/crcditcard/numbcr4019 2445.fg74.8/paymcntlist/paynicntinfo 1 /crcditcard/issucrhsbcjt55.9/paymentlist/paymentinf（） 1 /c red i t c ard/ex p i rat ion14/02azxc.10/paymenllist/paymenlinfo2798l.11/paymentlist/paymentlnfo /namegary allen34f7.12/paymentlist/paymentlnfo /credi（cardwe34.13/paymentlist/paym

23、entlnfo 2/creditcard/limit4000sxop.14/paymentlist/paymentlnfo /creditcard/currencygbplk69.15/paymcntlist/paymcntinfb|21/crcditcard/numbcr3920 4453 hjlg.16/paymentlist/paymentinfo2/creditcard/issuerlloyds tsbfdc4.17/paymentlist/paymentinfo2/creditcard/expiration13/05a1f23.第一步，从dtd中获取该文档所有可能的xpath路径表达

24、式，并将其结果插入到四 元组中,如表2中“xpath路径”列所示。第二步，通过xpath路径表达式获取每个路径在文档中对应的具体内容，并插入到四 元组中,如表2中“对应内容”列所示。第三步，牛成相应摘耍值。对于叶结点和属性值，可以直接采用hash算法生成其对 应的摘要值，如表2中“对应内容”列不为空的条1=1，并将牛成的摘要值插入到表2中“摘 要值”列。对于非叶结点，首先获取去所有孩子的摘要值并进行连接操作，然后将得到的连 接结果采用hash算法生成其对应的摘要值，按照自卜-向上的递推，最终可以产生跟节点 的摘要值。利用以上步骤生成的完整性检查池，用户可以验证任意分派xml数据的完整性。比如,

25、 将路/paymentlist/paymentlnfo2/creditcard对应的数据分派给某一用八，首先，该用 户在表屮査找对应的路径条目，如果条ii匹配成功，则表明文档屮确实存在这个路径；其次, 用户从检查池中获取该路径的所有孩子节点及元索属性的摘要值：a1f23, fdc4, hjlg, lk69, sxop,将这些摘要值进行连接操作产生字符串“a1f23fdc4hjlglk69sxop”， 并将产生的字符串采用hash算法生成一个摘要值，将生成的摘要值与检查池中路径 /paymentlist/paymentlnfo2/creditcard 对应的摘要值 “we34” 进行比较,如果相

26、同,则 表明分派给用户的数据内容是可信的，如果不同，则表明分派的数据发生了变化。到此，如 果川户对验证的结果依然怀疑，那么可以以此类推计算产牛根节点对应的摘耍值并进行比较。3结论本文利用xpath表达式來分解xml数据，以dom-hash为基础，产生xml数据完 整性检查池，用来检查分解xml数据完整性检查。利用xpath路径表达式，分解xml文 档和保持子文档的有效性变得简单起来。利用提出的完整性检查池，用户可以离线口主的检 査完整性，而不需要同其他川户协同。分析表明木文提岀的方法在实际屮是安全可行的。参考文献：1j wu, t-c., huang, c-c., guan, d.j., de

27、legated multisignature scheme with document decomposition j. the journal of systems and software, 2001 (55): 321-32&2 lu, e. j-l., chen, r-f., an xml multisignature scheme j. applied mathematics and computation, 2004(149): 1-14.3 geuer-pollmann, c., xml pool encryption c. in proceedings of the 2

28、002 acm workshop on xml security, nov. 22, 2002, fairfax va, usa. isbn: 1-58113-632-3. pp 1 -9.4 brandt, p., bontc, f., towards secure xml eb/ol. availabcl at: hltp://archivcs/piiblic/xml-cncryption/20000ct/atl-0016/02-discussion_papcr_s xml.doc (accessed on december 2009).5 stallings, w

29、., cryptography and network security: principles and practices m, fourth edition, isbn: 0131873164, by person education, inc., 2006, pp 341.6 rivcst, r.l., the md5 message digest algorithm s. rfc 1320. available at: /rfc/rfcl 321 .txt (accessed on feb. 2012).7 bertino, e., carminat

30、i, b., ferrari, e., thuraisingham, b., gupta, a., selective and authentic third-party distribution of xml documents jj. knowledge and data engineering, ieee transactions, 2004, 16(10): 1263-1278.integrity checking for xpath expression based xml document decompositionliu bao-long liu nian chen hua(school of computing & engineering, xi &#