基于域敏感指针分析的细粒度数据随机化技术

针对传统的数据随机化技术静态分析精度不高的问题,提出一种基于域敏感指针分析算法的细粒度数据随机化技术。在静态分析过程中,首先对中间表示进行语法抽象,得到形式化的语言表示;然后建立非标准类型系统,描述变量之间的指向关系;最后按照类型规则进行类型推断并求解,得到域敏感的指向关系。根据指向关系对数据进行随机化加密,得到经过随机化的可执行程序。实验数据表明,基于域敏感指针分析的数据随机化技术与传统的数据随机化技术相比,分析精度显著提高;处理时间开销平均增加了2%,但运行时间开销平均减少了3%。所提技术利用域敏感的指针分析,给程序带来更少的执行开销,并能够更好地提高程序的防御能力。     

基于SAT求解的面向对象程序类型分析

类型分析是面向对象程序分析中的重要环节,精确的类型分析能够提高其它程序分析的精度.由于传统精确分析方法固有的高复杂性,现有的类型分析大都使用粗糙的分析方法.提出了一种基于SAT求解的面向对象程序类型分析方法.该方法用命题逻辑表示类型在变量间的传递关系,将程序抽象成命题公式,并使用高效的SAT求解器求解,从而获得变量运行时的类型集合.该方法是流敏感的,并且具有良好的伸缩性,既可以进行快速但精度低的上下文不敏感分析,也可以进行较慢但精度高的上下文敏感分析.     

安全类型系统在编译技术中的应用研究

类型系统是一种设计和研究程序设计语言的形式化方法和工具。本文提出了一种新的用安全类型系统增强编译程序安全性的方法;给出了类型系统的形式化定义,引入了安全类型和安全类型系统的概念,并给出了安全类型系统的子类型规则和安全类型规则;最后讨论了安全类型系统在编译技术中的应用。     

类型系统λω×≤的PER模型

类型系统是近年来理论计算机科学的研究热点之一 .1999年周晓聪曾在文献 [1]中提出并研究了类型系统λω× ≤ 及其性质 .类型系统λω× ≤ 是λω×的扩充 ,引入了子类型关系和受限的全称类型 .与 System F的各种扩充相比 ,它区分各种上下文 ,使得规则和性质的研究更为清晰 .研究该类型系统的 PER模型作为其语义解释 ,并说明该模型的合理性     

XML 关键词检索的查询理解

与纯文本文档集相比,使用语义标签标注的半结构化的XML文档集,有助于信息检索系统更好地理解待检索文档.同样,结构化查询,比如SQL,XQuery和Xpath,相对于纯关键词查询更加清晰地表达了用户的查询意图.这二者都能够帮助信息检索系统获得更好的检索精度.但关键词查询因其简单和易用性,仍被广泛使用.提出了XNodeRelation算法,以自动推断关键词查询的结构化信息(条件/目标节点类型).与已有的推断算法相比,综合了XML文档集的模式和统计信息以及查询关键词出现的上下文及其关联关系等推断用户的查询意图.大量的实验验证了该算法的有效性.     

一种带约束的多态类型系统

本文讨论了一种带约束的多态类型系统,引入了约束类型,约束与全称量化的结合使得参数化多态函数的应用更安全,同时也为重工的表示和实现提供了一个新的途径,提高了类型表示的抽象度。本文讨论的类型系统具有两个不同层次的类型结构,约束的引入与肖去是不同层次上的操作,最后,本文人出了类型检查算法Ｗｒ,并证明了此算法中约束的可满足性是可判定的。     

流非敏感的跨过程的别名分析

数据流分析算法可以分类成流敏感和流非敏感两类。为了提高效率,流非敏感的跨过程分析没有利用与每个过程相关的过程内的控制流信息。文中,提出了一种流非敏感的数据流分析算法来计算指针引起的跨过程的别名问题。通过如下方法来提高了分析的精度:利用某些特定类型的注销(kill)信息,这些信息可以提前计算;计算每个过程内产生的别名信息,而不是只计算每个过程的出口点产生的别名信息。     

使用类型限定的系统依赖图检测整型错误

目前大多数的源码安全审计工具在整型错误的检测上具有局限性,往往只能检测整型溢出类型的漏洞。针对这个问题,对已有的系统依赖图（system dependence graph,SDG）检测模型进行了改进,结合类型限定理论提出了基于类型限定的系统依赖图（type-qualified SDG, QSDG）检测模型。该模型不仅可以用来检测C代码中潜在的绝大多数整型错误,而且还能根据其出错原因将其分类到所定义的八种错误类型。与SDG检测模型仅采用图同构算法进行检测相比,先使用类型推断算法再对QSDG进行检测可以降低检测所花费的时间。     

二进制程序整型符号转换缺陷的动态检测方法

针对符号转换错误引起缓冲区溢出的这类缺陷提出了一种面向二进制程序整型符号转换缺陷检测方法。以二进制插桩框架为基础,利用类型推断方法识别整型变量的符号类型信息,得到内存相关库函数中为冲突类型的参数的集合,并将其作为潜在的整型符号转换缺陷候选集。在中间代码层面插入检测代码做运行时检测,最终确定真正的整型符号转换缺陷。原型系统Sconvcheck的实验结果表明：该方法可以有效地检测出程序中的整型符号转换缺陷,并准确地定位错误发生的位置,而且误报率较低。     

Gdel语言编译时类型处理技术研究

Gdel是一种发展中的逻辑程序设计语言,目前还没有开发出编译器。Gdel语言的类型系统独特于通常的逻辑程序设计语言,语义上已初步形成了相应的描述方法,建立了严格的理论基础。按照传统的方法,逻辑程序的运行机制和Gdel语言的多态性决定了一些变量的类型和语义只能在运行时才能确定,把这类变量的类型检查放到程序运行中处理,势必增加许多额外的计算。提出了一种处理Gdel语言类型系统的编译技术。针对语言的类型,对其相关语法进行适当修改,通过类型推断,把变量类型的检查工作提前到编译阶段完成,可以较好地处理其变量类型的语义问题,同时减少了运行时类型检查工作,从而提高程序的运行效率。     

基于Open Type 的维哈柯文自动选形引擎的设计与实现

本文面向维哈柯文自动选择显示字形研究,分析了新疆地区普遍使用的维吾尔、哈萨克文和柯尔克孜文变形显示的特点,简要介绍了最新Open Type 字体技术的结构与操作步骤,基于该字体技术设计了一种通用维哈柯文自动选形引擎,通过分析文字的连接类型,构建自动选形规则库,按照规则绑定字形标签,并应用Open Type 字体解释引擎按照字形标签完成字符替换与置位操作。并且在永中office 维哈柯文版本上实现了该自动选形引擎, 经实际应用测试证明,该字体引擎完全实现了维哈柯文变形显示的要求。     

Presentation数学公式到Content转换关键问题研究

数学公式在计算机中的存储和表示格式多种多样,数学公式搜索中需要将各种格式的数学公式相互转换,从而为用户提供更为丰富搜索结果。从数学公式的用途和目的来看,计算机中的数学公式格式可分为Presentation型和Content型。主要研究和总结Presentation型数学公式到Content型数学公式的关键问题,提出基于类型系统的数学公式歧义推测方法,能够有效解决转换中的公式歧义问题。     

Proofs of a set of hybrid let-polymorphic type inference algorithms

We present a generalized let-polymorphic type inference algorithm, prove that any of its instances is sound and complete with respect to the Hindley/Milner let-polymorphic type system, and find a condition on two instance algorithms so that one algorithm should find type errors earlier than the other. By instantiating the generalized algorithm with different parameters, we can obtain not only the two opposite algorithms (the bottom-up standard algorithmW and the top-down algorithmM) but also other hybrid algorithms which are used in real compilers. Such instances’ soudness and completeness follow automatically, and their relative earliness in detecting type-errors is determined by checking a simple condition. The set of instances of the generalized algorithm is a superset of those used in the two most popular ML compilers: SML/NJ and OCaml. This work is supported by Creative Research Initiatives of the Korean Ministry of Science and Technology National Creative Research Initiative Center, http://ropas.kaist.ac.kr Work done while the third author was associated with Korea Advanced Institute of Science and Technology Hyunjun Eo: He is a Ph.D. candidate in the Department of Computer Science at KAIST (Korea Advanced Institute of Science and Technology). He recieved his bachelor’s degree and master’s degree in Computer Science from KAIST in 1996 and 1998, respectively. His research interest has been on static program analysis, fixpoint iteration algorithm and higher-order and typed languages. From fall 1998, he has been a research assistant of the National Creative Research Initiative Center for Research on Program Analysis System. He is currently working on developing a tool for automatic generation of program analyzer. Oukseh Lee: He is a Ph.D. candidate in the Department of Computer Science at KAIST (Korea Advanced Institute of Science and Technology). He received his bachelor’s and master’s degree in Computer Science from KAIST in 1995 and 1997, respectively. His research interest has been on static program analysis, type system, program language implementation, higher-order and typed languages, and program verification. From 1998, he has been a research assistant of the National Creative Research Initiative Center for Research on Program Analysis System. He is currently working on compile-time analyses and verification for the memory behavior of programs. Kwangkeun Yi, Ph.D.: His research interest has been on semanticbased program analysis and systems application of language technologies. After his Ph.D. from University of Illinois at Urbana-Champaign he joined the Software Principles Research Department at Bell Laboratories, where he worked on various static analysis approaches for higher-order and typed programming languages. For 1995 to 2003 he was a faculty member in the Department of Computer Science, Korea Advanced Institute of Science and Technology. Since fall 2003, he has been a faculty member in the School of Computer Science and Engineering, Seoul National University.     

程序设计语言的类型结构剖析

程序设计语言原理是计算机科学中的一个非常重要的领域,而程序设计语言的类型结构又是该领域中的一个非常重要的专题。文章结合当今广泛使用的C语言对程序设计语言的类型结构进行了深入的剖析,内容包括:内部非结构类型、枚举类型、有限映像(数组)、迪卡尔积(结构体)、判定或(共用体)、序列(串和文件)、指针等,并且适当地进行了举例说明。     

抽象类型在程序开发中的应用

本文邓开发中的抽象类，并给出了类型更改方法和类型实经的方法。本文还用例子说明了具体计算结构实现的方法。     

反编译中数据类型自动重构技术研究

类型重构作为反编译的关键问题,对程序的可读性及可理解性具有重要的作用。给出了汇编基础上数据类型自动重构的算法。对于简单类型,通过基于格的类型属性操作,用迭代算法来实现类型恢复;对于复杂类型,通过构建标记等价类来恢复结构化类型的框架,而后通过收集框架内可访问的偏移集合并利用简单类型恢复的算法对偏移对象类型进行恢复,从而推导出复杂结构类型。该算法是目前正在开发的类型重构工具的关键技术,它不仅能够准确地重构简单类型,而且能够准确地解析复杂类型,且准确率较高。     

一种等价于PI的二型模糊控制器设计算法

区间二型模糊集合将次隶属度做了简化,基于KM降阶算法的区间二型模糊控制器实现起来相对简单.虽然区间二型模糊控制器在一定程度上优于传统的一型模糊控制器或者PI控制器等,但区间二型模糊控制器并没有充分利用二型模糊集合的次隶属度信息.为解决这些问题,研究了普通二型模糊控制器的一般结构,提出了一种等价于PI的二型模糊控制器.该...     

Advantages of the Enhanced Opposite Direction Searching Algorithm for Computing the Centroid of An Interval Type‐2 Fuzzy Set

Computing the centroid of an interval type‐2 fuzzy set (IT2 FS) is an important operation in a type‐2 fuzzy logic system (where it is called type‐reduction), but it is also a potentially time‐consuming operation. In this paper, an enhanced opposite direction searching (EODS) algorithm is presented for doing this. The EODS comes from an early version of the IT2 FS type‐reduction method called the opposite direction searching (ODS) algorithm, which has been proven faster than the most commonly used Enhanced Karnik‐Mendel (EKM) method. The EODS differs from the ODS in two high speed formulas for calculating the centroid endings. Quantitative analysis on the mathematical operations and comparisons performed by EODS, ODS, and EKM algorithms shows that EODS could save about 50% of the calculations and comparisons in relation to ODS. Compared with EKM, it could save about 67% to 80% of the calculations and comparisons. Simulation experiments have been performed to compare EODS with the ODS and EKM methods in terms of average CPU time. The experimental results validate the quantitative analysis.     

Type error slicing in implicitly typed higher-order languages

Previous methods have generally identified the location of a type error as a particular program point or the program subtree rooted at that point. We present a new approach that identifies the location of a type error as a set of program points (a slice) all of which are necessary for the type error. We identify the criteria of completeness and minimality for type error slices. We discuss the advantages of complete and minimal type error slices over previous methods of presenting type errors. We present and prove the correctness of algorithms for finding complete and minimal type error slices for implicitly typed higher-order languages like Standard ML.     

一种新的区间二型模糊集合降阶算法

区间二型模糊集合的KM/EKM降阶算法,其效率较低,难以用于二型模糊逻辑的实时控制。而基于切换点计算公式的单调性关系的IASC和EIASC算法虽然其运算时间低于KM/EKM,但其初始值都是从两侧端点开始,其效率也有待提高。本文提出了一种新的二型模糊集合降阶算法,利用切换点计算公式和论域中值的关系以及初始化左右切换点的值来提高计算效率,2个仿真实例验证了本文算法的有效性和实用性。