基于抽象解释的可执行代码值范围分析

第３６卷　第２２期　计算机工程　２０１０年ｌ１月　ＶｏＬ３６　Ｎｏ．２２　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｎｏｖｅｍｂｅｒ　２０１０　・软件技术与数据库・　文章编号：１０００－－３４２８（２０ｉ０）２２－－－０面１．　—　————　基于抽象解释的可执行代码值范围分析　窦增杰，王震宇，姚伟平，陈楠，余弦　（解放军信息工程大学信息工程学院，郑州４５０００２）　摘要：阐述可执行代码抽象存储空间模型的概念并给出程序运行时刻环境抽象表示技术。通过抽象解释静态逼近程序不动点语义的理论　保证二进制代码数据流分析的正确性以及可计算性。基于抽象解释和单调数据流框架提出一种自动分析可执行代码变量取值范围的方法及　自动获取程序循环最大迭代次数和不可执行路径，并给出数据流分析实例。　关键词：抽象解释；值范围分析；数据流分析；运行时刻环境　Ｖａｌｕｅ　Ｒａｎｇｅ　Ａｎａｌｙｓｉｓ　０ｆ　Ｅｘｅｃｕｔａｂｌｅ　Ｃｏｄｅ　Ｂａｓｅｄ　０ｎ　Ａｂｓｔｒａｃｔ　Ｉｎｔｅｒｐｒｅｔａｔｉ０ｎ　ＤＯＵ　Ｚｅｎｇ－ｊｉｅ，ＷＡＮＧ　Ｚｈｅｎ－ｙｕ，ＹＡＯ　Ｗｅｉ－ｐｉｎｇ，ＣＨＥＮ　Ｎａｎ，ＹＵ　Ｘｉａｎ　（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，ＰＬＡ　ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ　４５０００２，Ｃｈｉｎａ）　｜Ａｂｓｔｒａｃｔ］Ｔｈｅ　ａｂｓｔｒａｃｔ　ｍｅｍｏｒｙ　ｍｏｄｅｌ　ａｎｄ　ｔｈｅ　ａｂｓｔｒａｃｔ　ｒｕｎ—ｔｉｍｅ　ｅｎｖｉｒｏｎｍｅｎｔ　ｏｆ　ｅｘｅｃｕｔａｂｌｅ　ｃｏｄｅ　ａｒｅ　ｄｅｓｃｒｉｂｅｄ．Ｔｈｅ　ｄａｔａ　ｌｆｏｗ　ａｎａｌｙｓｉｓ　ｉｓ　ｇｉｖｅｎ　ａｎｄ　ｔｈｅ　ｃｏｒｒｅｃｔｎｅｓｓ　ａｎｄ　ｃｏｍｐｕｔａｂｉｌｉｔｙ　ｏｆ　ｄａｔａ　ｆｌｏｗ　ａｎａｌｙｓｉｓ　ａｒｅ　ｅｎｓｕｒｅｄ　ｂａｓｅｄ　ｏｎ　ａｂｓｔｒａｃｔ　ｉｎｔｅｒｐｒｅｔａｔｉｏｎ　ｔｈｅｏｒｙ，Ａｂｓｔｒａｃｔ　ｉｎｔｅｒｐｒｅｔａｔｉｏｎ　ｉｓ　ｕｓｅｄ　ｔｏ　ｐｒｏｐａｇａｔｅ　ｔｈｅ　ｖａｒｉａｂｌｅ　ｖａｌｕｅ　ｒａｎｇｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｔｈｒｏｕｇｈ　ｔｈｅ　ｇｅｎｅｒｉｃ　ｍｏｎｏｔｏｎｅ　ｄａｔａｆｌｏｗ　ｆｒａｍｅｗｏｒｋ．Ｎｅｗ　ｍｅｔｈｏｄｓ　ｔＯ　ａｕｔｏｍａｔｉｃａｌｌｙ　ｃｏｍｐｕｔｅ　ｔｈｅ　ｍａｘｉｍａｌ　ｃｏｕｎｔｓ　ｏｆ　ｉｔｅｒａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ｌｏｏｐｓ　ａｎｄ　ｔＯ　ｉｄｅｎｔｉｆｙ　ｔｈｅ　ｉｎｆｅａｓｉｂｌｅ　ｐａｔｈｓ　ａｒｅ　ｐｒｅｓｅｎｔｅｄ．Ｔｈｅ　ｅｘａｍｐｌｅ　ｏｆ　ａｎａｌｙｚｉｎｇ　ｐｒｏｇｒａｍ’Ｓ　ｄａｔａ　ｌｆｏｗ　ｉｓ　ｇｉｖｅｎ．　［Ｋｅｙ　ｗｏｒｄｓＩ　ａｂｓｔｒａｃｔ　ｉｎｔｅｒｐｒｅｔａｔｉｏｎ；ｖａｌｕｅ　ｒａｎｇｅ　ａｎａｌｙｓｉｓ；ｄａｔａ　ｌｆｏｗ　ａｎａｌｙｓｉｓ；ｒｎｎ—ｔｉｍｅ　ｅｎｖｉｒｏｎｍｅｎｔ　１概述　据域∽Ｄ—Ｄａｔａ），抽象堆域　Ｄ～Ｈｅａｐ）和抽象栈域　Ｄ～Ｓｔａｃｋ）。　获取程序变量取值范围对程序的安全验证、属性检测、　每个抽象域均能表示程序运行时的属性，变量在具体存储空　漏洞发现都至关重要，要精确地获取变量的所有可能取值，　间的属性抽象表示成抽象区域中的属性。如图１所示，针对　需要找出从程序入口到变量执行点处所有可能的执行路径。　一个可执行文件，其抽象存储空问模型包含了一个抽象代码　但是寻找所有可能的执行路径是一个不可判定问题　ｊ，抽象　域，表示程序中的执行代码所在的区域；一个抽象数据域，　解释理论为计算机科学中的不可判定问题和复杂问题的逼近　表示程序所有初始化和未初始化的全局变量所在的区域；根　求解提供了系统性的构造方法和有效算法　Ｊ。程序的抽象解　据情况有若干个抽象堆域和抽象栈域。抽象栈域表示过程活　释使用另一个抽象对象域上的计算抽象逼近程序具体对象域　动记录所在的区域，抽象堆域表示动态分配产生的内存区域。　上的计算，使得程序抽象执行能够反映出程序真实运行的部　抽象存储空间模型就是抽象解释程序分析方法中抽象对象域　分信息　Ｊ。本文在可执行文件反汇编基础上，剖析汇编代码　的实例，基于抽象存储空问模型的运算反映了程序具体环境　的结构与特点，给出建立程序抽象存储空间模型和通过指令　上的运算。　迁移函数来获取运行时刻环境的方法，阐述了基于单调数据　流框架和抽象解释理论实现变量取值范围分析技术。　２基于抽象存储模型的代码运行时刻环境表示　２．１可执行代码存储空间抽象表示　每一个正在执行的程序可看作是在它的逻辑地址空间上　运行，程序逻辑地址空间由以下区域组成：　（１）代码区：存放可执行的目标代码。　（２）静态数据区：存放所有初始化和未初始化的全局变量　和编译器产生的其他数据。　ｆ３）堆区：存放程序运行时分配和释放的数据。　图１　程序抽象存储空间模型的基本构成　（４）栈区：存放过程的活动记录。　基金项目：国家“８６３计划”基金资助项目（２００７ＡＡ０１Ｚ４８３）；河南　在程序的实际逻辑空间中，程序的目标代码、活动记录、　省高新领域重点攻关基金资助项目（０８２１０２２１００１１）　堆区以及全局数据区在一个地址空间中。为了分析方便，把　作者筒介：窦增杰（１９８３一），男，硕上研究生，主研方向：信息安全，　逻辑空问抽象划分为互不相关的存储区域并分别对其建立抽　可信计算；王震宇，副教授；姚伟平、陈楠、余弦，硕士研　象存储模型。从而，程序存储空间不再是简单的一维地址空　究生　间，其包含了４类抽象域：抽象代码域（ＡＤ—Ｃｏｄｅ），抽象数　收稿日期：２０１０—０６—２４　Ｅ—ｍａｉｌ：ｄｏｕｚｅｎｇｊｉｅｌ２３＠ｇａｍｉｌ．ｃｏｍ　一６９一　２．２程序运行时刻环境的抽象表示　在程序抽象存储空间定义变量集合　ｖｎｒ垒ｒｅｇｉｓｔｅｒｕ　ｇｖａｒＵｆ＿ｖａｒＵ　ｈ＿ｖａｒ　—如下：　“　ｆ，　Ⅲｅｎｔｒｙ　１ｕ　ｆＤｕ　Ｉ　ｍ∈ｐｒｅｄ（ｎ）｝　其他　０　＝　（　）　其中，ｒｅｇｉｓｔｅｒ表示寄存器变量集合；ｇ＿ｖａｒ表示全局变量集　合；ｆ　ｖａｔ表示局部变量集合；　一ｖａｒ表示堆变量集合。　为了很好地处理不同字节内存读写操作，需要给出相应　的数值表示来精确地表示变量的取值。本文用带跨度的区间　域　表示变量的取值，　既能表示数值的范围又能表示数值　的变化幅度。　其中，，是程序开始结点的初始值，通常是Ｔ或者上；ｐｒｅｄ（ｎ）　表示节点　的前驱；　表示与节点ｎ对应的流函数；Ｕ为节点　的汇合函数。　４基于单调数据流框架变量值范围分析　４．１程序执行流的构造　可执行代码值范围分析需要确定基于程序执行流进行抽　定义１定义　垒｛ｘ＋ｉｘｍｌｉＥＺ｝，　表示Ｘ　ｍｏｄ　ｍ的同　余类。　定义２对于ｋ位的Ｓｌ：ｓ（１，“）表示下列整数集合：　Ｘｓ［１，“］）＝｛　∈［一２ｋ，２　］ｌｌ＜ｉ＜ｕ，　∈　）　基于Ｖａｒ和　，程序运行时刻环境抽象表示为：　Ｄ兰　ｒ＿÷Ｖ　，ｖｓ￣－（ｓｉＧｘ（Ｓ１ｐ）　ｘ（Ｓ／Ｈ）”）　其中，　表示抽象静态数据域中全局数据的数值集合（也表　示数值域）；　表示函数栈空问的数值集合；　表示函数堆　区间的数值集合；　＝（　）　ｘ（Ｓｌｐ）　Ｘ…ｘ（Ｓ／ｐ）　表示ｎ个栈区域　的数值集合；ＶＳ是一个完备格，对于ＶＳ。、ＶＳ　其上的偏序关　系ｒ－：ＶＳｌＥ　ＶＳ２，当且仅当ｖ　１是ＶＳ２的子集。定义如下操作：　（１）ＶＳｌＦ］ｌ￣ｓ２：ｖｓｌ和ｖｓ２的交集。　（２）ｖｓ１Ｕｖｓ２：ＶＳ１和ＶＳ２的并集。　（３）ｖｓ１＝ＶＳ１Ｖｖｓ２：加宽操作。　为了保证基于抽象存储模型的数据流分析迭代终止，本　文选择程序循环的汇合节点为加宽节点。　（４）０：表示各个抽象存储区域和整数Ｃ相加的结果。对　于ｖｓ＝（２，２［０，３］＋４）和ｃ＝６，贝０（ｖ　０ｃ）＝（８，２［０，３】＋ｌ　ｏ）。　（５）　（ｖｓ，Ｓ）：　（ｖ　，　）返回一个二元组（Ｆ，Ｐ）。其中，Ｆ表示“完　全访问”的变量集合，其中变量的大小为Ｓ，起始地址在ＶＳ　中；Ｐ表示“部分访问”的变量集合，Ｐ中所包含的变量有　２种：起始地址在Ｉ）Ｓ中，大小不等于Ｓ；变量的地址在ＶＳ中，　但它的起始地址和大小并不满足Ｆ中的条件。　（６）ＲｅｍｏｖｅＬｏｗｅｒＢｏｕｎｄｓ（ｖｓ）：边界最小化，把　的下界　设定为一ｏＯ。　（７）ＲｅｍｏｖｅＵｐｅｒＢｏｕｎｄｓ（ｖｓ）：边界最大化，把　，的上界设　定为０（３。　３数据流方程的建立　数据流分析通过静态分析程序的结构及静态收集程序中　各个变量的引用情况建立数据流方程，对数据流方程进行求　解以得到程序的属性信息。程序的变量、表达式的性质或者　变量的取值等程序属性可抽象表示为格中的元素。格到格自　身的映射函数　Ｌ一￡称为流函数。流函数通过格到格自身的　映射来模拟程序的运行。程序流图Ｇ（Ｎ，Ｆ）中Ⅳ表示程序指令　对应的结点，Ｆ为程序的执行流。　对于一个程序流图Ｇ（Ｎ，　和格Ｌ，以前向数据流分析为　例，对于每个节点ｎ，有：　（１）　：节点ｎ之前程序点的属性集合，即ｎ的入口处的　数据流信息。　（２）ＯＵＴｎ：节点ｎ之后程序点的属性集合，即ｎ的出口处　的数据流信息。　（３　：节点ｎ的流函数，　根据　计算ＯＵｒｎ。　对所有的ｎＥＮ和格Ｌ，　∈Ｌ，０ＵＴ，∈Ｌ，数据流方程　一７ｆ卜一　象解释的迭代序列。为表示程序的迭代序列，需要对可执行　代码反汇编结果进行处理，使每条汇编语言带有标号。程序　的标号集合定义为Ｌａｂ。定义函数ｉｎｉｔ：ｌ－－＊Ｌａｂ返回指令集合，　的初始标号；函数ｆｉｎａｌ：Ｉ－－－￣　，Ｊ口６）返回指令结束标号的集合；　函数ｆｌｏｗ：Ｉ－－＋￣Ｊ（ＬａｂｘＬａｂ）映射指令的执行流集合，。　４．２指令迁移函数　数据流方程的流函数在此实例化为指令迁移函数。指令　迁移函数描述一条指令执行前后程序抽象运行时刻环境的变　化情况，指令迁移函数输入一个抽象运行时刻环境并返回一　个新的抽象运行时刻环境。表１列出了汇编指令类型；Ｒ１、　Ｒ２是寄存器；Ｃ、Ｃ１、Ｃ２为整型常量。　表１汇编指令类型　表２列出了各类型汇编指令对应的迁移函数　。其中，　ｒｌ与　，　与ｒ，４的抽象迁移函数相似，在此仅列出　与　的抽象迁移函数。指令执行前后的程序抽象运行时刻环境分　别记为　。　表２指令迁移函数　类型　抽象运行时刻环境　２Ｈｖ　，∈６　：＝ｄＲ，¨（　，０Ｃ）】　ＲｌＨ　∈　２ＨＶ　∈　Ａ　：＝　Ｒ　ＬＨ（ｗＲｌ＠ｖｓＲ　）ｌ　２ＨＶ　∈　（　，Ｐ）＝　（ｖ　＠Ｃｊ，　）　Ａｄ　ｉｆＩＰＩ＝０ｔｈｅｎ　ｖｓ　＝ｕ｛ＶＳ　Ｉｖ∈Ｆ，ｖＨｖ　｝　：＝ｏｌＲｌＨ（ｖ　０Ｃ２）】　ｅｌｓｅ　：：　ＲｌＨＴ】　Ｒ１　＿ｖ　．∈　２Ｈｖ　∈ｏ，（　，Ｐ）：　（ｖｓ　．＠Ｃ　Ｅ，　）　ｔａｒｐ＝ｉｆ－（　ｌ　∈（ＰＵＦ）｝ｕｆｐＨＴｌＰＥＰ｝　Ａ　ｉｆＩＦＩ：Ｉ，ＩＰ［：０【ｈｅｎ　：：　ｆ　ｐｕ（ｖ　（ｖｓＲ￣￣Ｃ２）『ｖ∈　｝］　ｅｌｓｅ　：＝　ｆ　Ｕ｛ｖＨ（ｖ　＠Ｃ２）Ｕｖｓ　ＩｖＥＦ，Ｖ￣，ＶＳ　∈盯｝】　４．３基于单调数据流框架程序值范围分析算法　一个单调数据流框架等价于一个完备格：　Ｌ＝（Ｌ，Ｅ，Ｕ，ｎ，Ｔ，上）　单调数据流框架的实例由以下构成［４１：　（１）框架的完备格Ｌ；　（２）指令迁移函数集合厂；　（３）通过函数ｆｌｏｗ返回的流集合Ｆ　（４）程序的极值标号集合Ｅ，　＝｛ｉｎｉｔ（１）１；　（５）极值２∈，Ｊ，极值表示程序入１３点的初始值；　（６）标号　对应的指令迁移函数　。　使用单调数据流框架来求解变量取值范围就是求下面等　式的最小不动点。　Ｒ。（　）＝ｕ｛Ｒ（１　）Ｉ（，　，，）∈，｝ｕ纽　Ｒ．（ｆ）　（Ｒ。（ｆ））　‘一一Ｊ／１上－ｉｅｌｆ　ｓｅ　ｆ∈Ｅ　上式中的Ｒ表示程序的抽象运行时刻环境，Ｒ。（ｆ）和Ｒ．（ｚ）　分别表示标号为ｆ指令执行前后的运行时刻环境。基于单调　数据流框架　的求解算法如下所示：　算法变量值范围分析迭代算法　输入（Ｌ１　Ｆ，Ｅ，ｚ　输出Ｒ。（ｆ）；Ｒ．（ｆ）　Ｉｎｉｔｉａｌｉｓａｔｉｏｎ　０　Ｗ：＝ＮＵＬＬ　ｆｏｒ　ａｌｌ（１，１　）∈Ｆ　ｄｏ　Ｗ：＝ｃｏｎｓ（（１，１　），Ｗ）　ｅｎｄｆｏｒ　ｆｏｒ　ａｌｌ（１∈ＦＩＩ∈Ｅ）　ｉｆ　１∈Ｅ　ｔｈｅｎ　Ｒ。（１）：＝ｚ；ｅｌｓｅ　Ｒ。（１）：＝Ｊ－　ｅｎｄｆｏｒ　Ｉｔｅｒａｔｉｏｎ（）　ｗｈｉｌｅ　Ｗ￣ＮＵＬＬｄｏ　ｌ：＝ｆｉｒｓｔ（ｈｅａｄ（Ｗ））　ｌ　：＝ｓｅｃｏｎｄ（ｈｅａｄ（ｗ）），Ｗ：＝ｔａｉｌ（Ｗ）　ｉｆ　ｆｌ（Ｒ。（１））≠Ｒ。（１　）ｔｈｅｎ　Ｒ。（１　）：＝Ｒ。（１　）Ｕｆｌ（Ｒ。（１））　ｆｏｒ　ａｌｌ　ｌ＂ｗｉｔｈ（１　，１”）∈Ｆ　ｄｏ　Ｗ：＝ｃｏｎｓ（（１　，１”），ｗ）　ｅｎｄｆｏｒ　ｅｎｄｗｈｉｌｅ　其中，ｗ由Ｆ中的元素组成；函数ｃｏｎｓ用于向ｗ中插入元　素（ｆ，ｌ　）；函数ｈｅａｄ用于取ｗ的第１个元素；函数ｆｉｒｓｔ用于　取（，，ｆ　）中的第１个成分；函数ｓｅｃｏｎｄ用于取（，，ｆ　）中的第２个　成分。　５约束条件优化及分析实例　定义３通用单调数据流框架下分析实例（Ｌ　Ｆ，Ｅ，ｚ√），一　条程序执行路径为标号序列　＝　一，　】，ｎ＞０，ｌｂｌｎＥｌａｂ，　【ｆｉ’ｆＩ＋ｌ】ＥＦ，ｉ＝１，２，…，ｎ一１，定义路径的迁移函数为：　Ｒ）：｛　伸・）ｐ　＝０Ｅ０…　・：　，　一　－：　（Ｒ）　命题１对于分析实例（Ｌ　Ｆ，Ｅ，ｚ　，路径ｐ＝［Ｗ２，…，ｆ　】为　程序一条路径。当迭代完成后，Ｒ对应于１　的程序抽象运行　时刻环境，　ｉ　（　）。如果存在变量ＰａｒｅＶａｒ，使得　（ｖ口一≠　，　但Ｒｐ（ｖａｒ）＝Ｏ，则Ｐ为不可执行路径。　命题２对于分析实例（Ｌ，　Ｆ，Ｅ，ｚ　，ｖａｒ为循环变量集合，　则循环的迭代次数为：　ｌｏｏｐｃｏｕｎｔ＝ｍｉｎｊ（｛　一１　Ｊ＋１），ｊｃＦａｒ　其中，变量　为　形式：ｓ［１，Ｍ］。　为了说明上述数据流求解过程，下面给出一段源码：　ｉｎｔ　ｚ＝１：　ｍａｉｎ（）　（　１ｎｔ　ｘ，Ｙ；　ｆｏｒ（ｘ：Ｏ；ｘ＜２Ｏ；ｘ＝ｘ＋２）　｛　ｉｆ（ｘ＜２５）　ｙ＝ｘ＋ｚ：　ｅｌｓｅ　ｙ＝ｚ；　｝　）　对生成的可执行程序反汇编得到的精简汇编代码如下：　ｐｒｏｃ　ｍａｉｎ　ｅｄｘ：＝［４０５０３０］　ｅｃｘ：＝ｅｃｘ—ｅｃＸ　ｉｆ（ｅｃｘ＜１９ｈ）　ｔｈｅｎ　ｅａｘ：＝ｅｄｘ＋ｅｃｘ　ｅｌｓｅ　ｅａｘ：＝ｅｄｘ　ｅｃｘ：＝ｅｃｘ＋２　ｉｆ（ｅｃｘ＜１４ｈ）　ｔｈｅｎ　ＪＭＰ　３　ｅｌｓｅ　ｒｅｔｎ　ｍａｉｎ函数的抽象存储模型涉及２类抽象域，一个是ｍａｉｎ　函数的抽象栈域，另一个是抽象全局数据域。其抽象存储空　间模型如图２所示，全局变量０ｘ４０５０３０在抽象全局数据域中　用Ｍｅｍ一１来表示，其偏移为Ｇｌｏｂａｌ＋１。　ＥＡＸ　ＥＣｘ　ＥＤＸ　图２实倒的抽象存储空向模型　对汇编代码分析得代码的流集合：　Ｆ＝｛（１，２），（２，３），（３，４），（３，５），（４，６），（５，６），（６，７），（７，８），（７，９），（８，３）ｌ　根据表２的迁移函数，变量值范围分析数据流方程求解　公式为：　Ｒ。（１）：ｅ　＝¨（上，上）；　ｃ　＿（Ｌ上），　Ｈ（上，上），　Ｌｌ　（１，上）　Ｒ．（１）＝＿厂Ｉ（Ｒ。（１））：Ｒ。（１）Ｉ　（如　一十（１，＿＿＿）ｊ　Ｒ。（２）＝尺．（１）　Ｒ．（２）＝＿７　（Ｒ。（２））＝尺。（２）［ｅｃｘ￣－－＋（Ｏ，上）］Ｒ。（３）＝Ｒ。（３）ＶＲ．（２）ＭＲ．（８）　Ｒ．（８）ｉ　（　。（８））＝　（８）　迭代完成后得到的变量取值范围为：　Ｒ．（１）：ｅａｘ＝Ｈ（上，上），ｅｃ　Ｈ（上，ｊ＿），ｅｄｘ卜＿÷（１，上）　Ｒ．（２）：ｅａｘ＝Ｈ（２，上），ｅ　Ｈ（０，上），Ｐ　Ｈ（１，上）　．　（３）：ｅａｘ＝Ｈ（上，＿Ｌ），ｅｃｘＨ（２［Ｏ，９］，＿Ｌ）　Ｒ．（４）：　＝Ｈ（２【０，９］＋ｌ，＿＿），ｅｃｘ￣－－＊（２［Ｏ，９１，ｊ－）　Ｒ．（５）：８似＝卜＿＋（１，上），ｅｃ　Ｈ（　，上）　Ｒ．（６）：ｅａｘ＝￣－－ｆ２［Ｏ，９】十ｌ，上），ｇｃ　（２【Ｏ，１０】，上）　根据以上获得的取值信息，标号３处其中循环变量为　ｅｃｘ，由此可知循环迭代次数为ｌｏｏｐｃｏｕｎｔ＝ｍｉｎ　。（１“一１　ｌ＋１）＝　Ｌ９—０Ｊ＋１＝１０。　对于路径　Ｊ＝ｆ１，２，３，５】，月　ｌｉ　（ＲｐＩ）ｉ　（月Ｉ））））：ｅａｘ＝　Ｈ（１，上），ｅｃｘ￣－＋（ＳＪ，上）；对于路径ｐ２＝［１，２，３，４】，Ｒｐ２：ｆｐ（Ｒｐ２）＝　（下转第７４页）　一７１—　ｄ的意义同表ｌ。　表２　ＤＫＭＥＡＮＳ算法的重要步骤所需的通信时问　重要步骤　通信时间　ｋ（　ｋ（　ｋ（　．　．　本文用（１个处理机所用时间）÷（多个处理机所用时间）计算加　速比，结果见表５。　表５加速比　。　Ｐ　）　。＋ｐｄＴｄｍ）　ｐｄ　ｔ　）　＋口　．　表３　ＰＫＭＥＡＮＳ算法酌重要步骤所需的运算时问　重要步骤　运算时问　从表５可以看到，实际的加速比和式（５）的理论值非常接近。　另外，计算通信比也是一个常用的衡量指标，计算通信　ＰＫＭＥＡＮＳ的通信时间　ｏｍｌｌｌ＝（３ｋ＋１）Ｔｓ【ａｒｔ　ｐ＋２（１＋　，ｔ￣＝ＴｓｌＴｐ，结果见表６。通过实测的计算结果，计算通信比也　较高。　表６通信比　由于　、　在特定的环境中为常数，因此通信的　时间复杂度约为Ｏ（ｐｋｄ）。　～　却＋（ＰＫＭＥＡＮＳ计算时间　。　ｐ＝（（　＋　＋１）　＋１　）　。ｐ，　理论值　Ｉ．５ｘｌＯ　３．Ｏｘ１０　竺塑苎　４　５￣１０　６．０ｘｌ０　７．５ｘ１０　．　９．０ｘｌ０　由于　。。在特定的环境中为常数，且ｎ远大于ｋ、ｄ，因此计　算的时间复杂度约为Ｏ（ｋｄｎ／ｐ），它比通信时间复杂度更高阶，　说明该问题值得并行。　２６．９１６　７　４２．３ｌ２　５　３６．１４８　ｌ　５５．９５８　３　４８．２６４　７　４３　４１３　０　２０　０００　０　１　８．７０５　９　１９．２４０　０　２２　１０３　４　２２　８８５　７　２０　４２５　５　１３　８７５　０　１９．３６３　６　１５　８５０　０　１５．１４２　９　３９．５７１　４　２１．３３３　３　１Ｉ　４２８　６　１７．７７７　８　Ｉ２．４７３　７　１５１４２　９　１４　３２Ｉ　４　Ｉ６　４００　０　９　１４２　９　８．０００　０　１３．６４２　９　１６．０００　０　１２．２６９　２　１４．６９２　３　ＰＫＭＥＡＮＳ所需时间　：　。　。＋　。　，每次迭代的时问　复杂度约为Ｏ（ｋｄｎ／ｐ）。同样，对于式（２），算法ＳＫＭＥＡＮＳ每　次迭代的时间复杂度约为Ｏ（ｋｄｎ）。　加速比系数＝　１６结束语　本文对串行ｋ均值聚类算法的并行进行了研究，给出了　（５）　ｋｄｎ＝ｐ　Ｋｎｎ｜Ｄ　文献【６】认为，对于Ｐ个处理机而言，可能获得的最大加　速比通常为Ｐ，从式（５）可见，算法ＰＫＭＥＡＮＳ具有很高的　性能。　２个定理，从而保证了在减少计算节点间通信代价的情况下，　能从局部聚类信息生成完备的全局聚类信息。在此基础上，　实现了基于ＭＰＩ的并行ｋ均值算法。通过实验和性能分析证　明了理论分析的正确性。　５实验　本次实验所用的数据参照ｈｔｔｐ：／／ａｒｃｈｉｖｅ．ｉｃｓ．ｕｃｉ．ｅｄｕ／ｍｌ／上　的Ｉｒｉｓ数据集的特点，随机生成样本数分别为１．５ｘ１０。、　３．０ｘｌ０。、４５ｘｌＯ。、６０￣１０。、７５ｘ１０。、９ＯｘｌＯ。的６个数据集。　．参考文献　［１］Ｄｈｉｌｌｏｎ　Ｉ　Ｓ，Ｍｏｄｈａ　Ｄ　Ｓ．Ａ　Ｄａｔａ—ｃｌｕｓｔｅｒｉｎｇ　Ａｌｇｏｒｉｔｈｍ　ｏｎ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｍｅｍｏｒｙ　Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ［ＥＢ／ＯＬ］．（１９９９—１０・２０）．ｈｔｔｐ：／／ｗｗｗ．ＣＳ　ｒｐｉ．　ｅｄｕ／￣ｚａｋｉ／ＷＫＤＤ９９／ｄｈｉｌｌＯｉｌ．ｐｓ．ｇｚ．　．．．实验所用硬件环境为：２．０　ＧＨｚ　ＣＰＵ，１２８　ＭＢ内存，软件环　境为Ｕｂｕｎｔｕ８．１０和ＭＰＩＣＨ１．２．７。实验分别在１台、２台、　［２］倪巍伟，陈耿，孙志挥．一种基于数据垂直划分的分布式密度　聚类算法［Ｊ】．计算机研究与发展，２００７，４４（９）：１６１２：１６１７．　［３１　Ｊｏｓｈｉ　Ｍ　Ｎ．Ｐａｒａｌｌｅｌ　Ｋ—ｍｅａｎｓ　Ａｌｇｏｒｉｔｈｍ　ｏｎ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｍｅｍｏｒｙ　Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ［ＥＢ／ＯＬ］．（２００３－１０－１０）．ｈｔｔｌ：ｌ：／／ｗｗｗ．ｃｓ．ｕｍｎ．ｅｄｕ／～　４台、６台、８台、１Ｏ台微机上进行，结果如表４所示，表中　的数据为每次迭代所用的计算时间和通信时间。　一４　粤　—・・　－：＿—＿：＿・　一：＿—＿：．　［４１　ｍ谷ｎ淑ｉｏｓ化ｈｉ／吕维先，ＰＫＭｅａｎｓｐｄｆ．●　．基于消息传递的并行聚类算　法…．现代计算机，２００６，（１）：２２７—２３０．　［５】Ｈａｎ　Ｊｉａｗｅｉ，Ｋａｍｂｅｒ　Ｍ．Ｄａｔａ　Ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ　ａｎｄ　Ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，ＵＳＡ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ，２０００．　ｆ６】Ｗｉｌｋｉｎｓｏｎ　Ｂ，Ａｌｌｅｎ　Ｍ．并行程序设计［Ｍ】．陆鑫达，　译．北京：高等教育出版社，２００６．　４０２－４０３．６　：　妻　苎　萼竺　墨　示　【３】　…Ｇ．　Ｙ。　。ｓ。。　Ｎ。　ｗｈ砒Ｙ。　Ｅ　∞　【Ｄ］　．吝　出　堑　：　车些荸　圭　婺塑　２　方　妻　量　警围。　：　。。㈣ｎ　ＵＳ　Ａ：Ｔｈｅｕ　ｉｖｅｒｓｉｔｙｏｆｗｉｓｃｏ　ｓｉｎ．　２００７￣　‘　翌　［４］　洛．妄时系统最差情况执行时间分析　研究［Ｄ］．长沙：国　而提高可执行程序分析效率鬯　法，　一　莘技某ｌ吴；　………‘　…～一’。　为程序的安全验证、属性检测、　…　‘’。　编辑顾逸斐　．　抽墨　竺塞　苎　堑　理　。鱼缸…　…一…２　……　．幽　篓　；　，’　嚣　一　”　一　…　象解释理论的程序验证　，　　．．　，