基于命题逻辑的DNS可解析性量化评估模型  

Quantitative evaluation model of DNS resolvability based on propositional logic

作　　者：杜跃进[1,2,3] 张兆心[1,4] 王克[1] 杨逍[1] 胡萍[1] 

机构地区：[1]哈尔滨工业大学,哈尔滨150001 [2]国家计算机网络应急技术处理协调中心,北京100029 [3]北京邮电大学,北京100876 [4]中国科学院计算技术研究所,北京100190

出　　处：《高技术通讯》2013年第2期116-122,共7页Chinese High Technology Letters

基　　金：863计划(2007AA010503);国家自然科学基金(61100189,61003261);山东省中青年科学家奖励基金(BS2011DX001);威海市科技攻关(2010-3-96);哈尔滨工业大学科研创新基金(HIT.NSRIF.2011119)资助项目

摘　　要：针对DNS可解析性量化评估问题,提出了基于命题逻辑的DNS可解析性量化评估方法。该方法通过对域名解析依赖关系的分析建立域名解析依赖关系图,结合命题逻辑将域名对DNS服务器的依赖性转换为逻辑图,进而将域名的可解析性问题转换为数理逻辑中的命题公式的可满足性问题;通过对命题公式进行析取范式的转换和对命题变项数最少的简单合取范式的分析,获取域名可解析的最小DNS服务器组合,从而指导DNS服务器的布置和规划;通过对命题公式进行合取范式的转换和对命题变项数最少的简单析取范式的分析,获取域名不可解析的最小DNS服务器组合,从而对这些DNS服务器进行重点防护。以Alex Top 1000域名为例分析了解析依赖关系,经统计计算发现,Alex Top 1000域名解析平均依赖DNS数量为5.58个;域名解析依赖的最小服务器组合在[1,4]区间内,平均值为1.41个;破坏域名解析的最小服务器组合在[1,6]区间内,平均值为2.44个。To solve the problem of quantitative evaluation of DNS resolvability, a method for quantitative evaluation of DNS resolvability based on propositional logic is presented below ： establishing the dependence relation graph of do- main name resolution through analyzing the dependence of domain name resolution, and transforming the dependen- cy of a domain on a DNS server into a logic graph using the propositional logic ; finding the smallest name-resolvable DNS server set through the proposition formulae＇ s DNF （ disjunctive normal form） transformation and the analysis of the simple CNF （conjunctive normal form） with the minimum number of propositional variations to direct the lay- out of servers ; making proposition formulae＇ s CNF transformation and the analysis of the simple DNF with the mini- mum number of propositional variations to find the smallest name-resolvable DNS servers to emphatically protect the DNS servers. Based on the analysis of the Alex top 1000 domain, it can be found by statistical calculation that the average dependent DNS number of resolution in Alex Top 1000 is 5.58, the mini-number servers of domain resolu- tion are in [ 1,4] with the average number of 1.41, and the mini-number servers of damaging domain resolution are in [ 1,6 ] with the average number of 2.44.

关 键 词：域名系统(DNS) 可解析性 量化评估 命题逻辑 

分 类 号：TP393.05[自动化与计算机技术—计算机应用技术]