登录
首页 » Others » 最大团问题(回溯法/分支限界法)

最大团问题(回溯法/分支限界法)

于 2020-11-29 发布
0 225
下载积分: 1 下载次数: 3

代码说明:

问题描述 图G=(V,E)的一个团是图G的一个完全子图,即该子图中任意两个相异的顶点都有一条边相连。最大团问题就是要找出图G中顶点数最多的一个团。基本要求(1) 用回溯法来求解最大团问题。(2) 用分支限界法来求解最大团问题。测试数据 由读者给定若干连通图。实现提示 本课程设计的实现主要包括以下主要过程:(1) 关于解的编码形式(对应顶点i 的变量x[i]=1当且仅当顶点i属于找到的最大团)。(2) 设计合适的上界函数,即如何确定当前团最大顶点数的上界。

下载说明:请别用迅雷下载,失败请重下,重下不扣分!

发表评论

0 个回复

  • 基于Qt的实时曲线绘制
    利用第三方类QCustomPlot在Qt环境中进行实时曲线绘制
    2020-11-27下载
    积分:1
  • 直流电机双闭环simulink仿真
    直流电机双闭环调速系统simulink仿真程序
    2020-12-05下载
    积分:1
  • 2013数学建模国赛B思考过和模型还有代码(适合初学者)
    这个是2013数学建模国赛B题的一个完整的解答过程,包括了对题目的思考,模型的建立,代码的编写,论文的写法。当然还包括了最终的结果-----完整的报告。
    2021-05-06下载
    积分:1
  • ANSYS_WORKBENCH设计、仿真与优化
    《ANSYSWorkbench设计、仿真与优化》以最新版ANSYSWorkbench11.0为依据,以工程人员产品设计的流程为主线,由浅入深地介绍了ANSYSWorkbench在产品设计、仿真与优化过程中的具体功能、使用方法和应用实例。ⅣANSYS Workbench设计、仿真与优化4.2.1基础…………484.2.2分析关键………494.2.3分析步骤……………………………………494.3振动电机轴谐响应分析……………….544.3.1基础………………54………54.3.3分析步骤……………………………………………………………554.4机柜随机振动分析…………………………………………………………614.4.1基础……………………………………………………………614.4.2分析关键…………………………………………………624.4.3分析步骤………………………………………………………62第5章机构运动学分析…………………675.1机构运动学分析基础………………………………………………………675.2轻型打桩机机构运动学分析……………………………………685.2.1工程背景……………………………………………5.2.2分析关键…………………………………………685.2.3分析步骤…………69第6章热力学分析………………………………………756.1热分析基础…………………………………………………………756.2汽缸盖稳态温度场分析……………………………………………766.2.1工程背景766.2.2分析关键………………………………………………………776.2.3分析步骤……………………………………776.3涡轮增压器涡壳瞬态温度场分析和热应力分析………………………………806.3.1工程背景………………………………………………806.3.2分析关键………6.3.3分析步骤…………………………81第7章疲劳分析……………………………………………………867.1疲劳分析基础……………………………………:867.1.1疲劳分析定义……………………………………………867.1.2 AWE Fatigue程序处理疲劳问题的过程………………862按键疲劳分析………………………………………………………877.2.1工程背景………………………………………………………877.2.2分析关键…………………887.2.3分析步骤…………………………………………………887.3轮毂疲劳分析………………………………………………………………92日录7.3.1工程背景………927.3.2分析关键………27.3.3分析步骤……93第8章优化设计……………………………………………………………………968.1优化设计基础……………………………………………968.1.1优化设计的基本原理…968.1.2优化设计的分类………………………………………………………978.1.3AWE优化设计的分析步骤………………988.2支架拓扑结构优化设计………………………………………………………998.2.1工程背景………8.2.2分析关键…………………………………………998.2.3分析步骤…98.3散热器形状优化设计……………………………………………………………1028.3.1工程背景………………………………………………………1028.3.2分析步骤…………………103第9章二次开发1109.1二次开发基础………………………………………………………11109.2参数化程序设计语言……………………………………………………1109.2.1APDL简介…………………………1109.2.2APDL的参数和宏………………………………………………1119.2.3气动刹车装置非线性分析12…………………………119.3用户操作向导……………………1159.3.1 Wizard简介…………………………………………………………1159.3.2操作向导编辑器…………………………………11169.4客户化定制…………1179.4.1SDK简介………………………………………………………………1179.4.2客户化定制实例…………………………………………………118第1章 ANSYS Workbench基础1.1 ANSYS Workbench概述随着计算机辅助工程(CAE)技术在工业应用领域中的广度和深度的不断发展,它在提高产品设计质量、缩短周期、节约成本方面发挥了越来越重要的作用。目前,CAE分析的对象已由单一的零部件分析拓展到系统级的装配体,如飞机、汽车等整机的仿真。同时,其分析的领域已不再仅仅局限于结构力学,已涉及流体力学、热力学、电磁学、多场耦合等更加丰富的物理空间。而且,CAE分析不再仅仅是专职分析人员的工作,设计人员参与CAE分析已经成为必然ANSYS Workbench Environment(AwE)作为新一代多物理场协同CAE仿真环境,其独特的产品构架和众多支撑性产品模块为产品整机、多场耦合分析提供了非常优秀的系统级解决方案。它所包含的3个主要模块:几何建模模块( Design Modeler)、有限元分析模块( Design Simulation)和优化设计模块( Design Xplorer)将设计、仿真、优化集成于一体,可便于设计人员随时进入不同功能模块之间进行双向参数互动调用,使与仿真相关的人、部门、技术及数据在统一环境中协同工作。具体来讲AWE具有的主要特色如下。1.强大的装配体自动分析功能针对航空、汽车、电子产品结构复杂,零部件众多的技术特点,AWE可以识别相邻的零件并自动设置接触关系,从而可节省模型建立的时间。而现行的许多软件均需要手动设置接触关系,这不但费时同时还容易出错。除此之外,AWE还提供了许多工具,以方便手动编辑接触表面或为现有的接触指定接触类型。AWE提供了与CAD软件及设计流程之间的无与伦比的整合性,从而发挥CAE对设计流程最大限度的贡献。最新的AWE使用接口,可与CAD系统中的实体及曲面模型双向连接,具有更高的CAD几何导入成功率。当CAD模型变化时,不需对所施加的负载和支撑重新定义。AWE与CAD系统的双向相关性还意味着,通过AWE的参数管理可方便地控制CAD模型的参数,从而提高设计效率;AWE的这一功能,还可对多个设计方案进行分析,自动修改每一设计方案的几何模型。2.自动化网格划分功能许多CAE用户都花大部分的时间在建立网格上,AwE在大型复杂部件,如飞机组装配件的网格建立上独具特色,自动网格生成技术可大大节省用户的时间。根据分析类型不同,有很多因素影响分析的精度。传统的专业分析人员花大量的时间和训练来掌握各种分析,手动处理模型以保证分析的精度;而对于设计人员来讲,他所关注的应该是自己的产品设计,而不是有限元方法,因此需要一个可靠的工具来替代传统的工具,尽可能实现自动化。AWE的自动化网格划分功能如下:自适应网格划分,对于精度要求高的区域会自动调整网格密度ANSYS Workbench设计、仿真与优化·自动化网格划分,生成形状、特性较好的元素,保证网格的高质量。·自动收敛技术,是自动迭代过程,通过自适应网格划分以使指定的结果达到要求的精度。例如,如果对装配中某一个零件的最大应力感兴趣,可指定该零件的收敛精度。·自动求解器选择,AWE根据所求解问题的类型自动选择适合的求解器求解。智能化的负载和边界条件自动处理。3.协同的多物理场分析环境及行业化定制功能CAE技术涵盖了计算结构力学、计算流体力学、计算电磁学等诸多学科专业,而航空产品的设计对这几个学科专业都有强烈的CAE需求。单个CAE软件通常只能解决某个学科专业的问题,导致使用者需要购买一系列由不同公司开发的、具有不同应用领域的软件,并将其组合起来解决其实际工程问题,这不但增加了软件投资,而且很多问题会由于不同软件间无法有效而准确地传递数据而根本不能实现真正的耦合仿真计算。目前,全面的、真正的“多物理场耦合分析”(如图1.1所示)时代已经来临,多场分析能力已经成为现代CAE软件技术水平的重要标志。多组分/多相流}(流体力学)[可压缩流H高级辐射高级疲劳高度非线性共轭传热结构力学多物理场耦合(温度场非线性非线性/辐射时/频域动力稳态/瞬态线性静力低频电磁场}(电磁场)M高导/对流图1.1现代高级CAE软件AWE组合分析能力4.快捷的优化工具 DesignXplorerAWE本身既是一个成熟的多物理场协同CAE仿真平台,又是一个基于最新软件技术的开放式开发平台,利用其开发包 Workbench SDK可以非常便捷地实现诸如专用程序开发、流程自动化和简化、专家经验的保存和固化、分析规范的保存和固化、自有程序的包装、其他程序的集成等众多的用户化开发功能。在 Workbench基础上,设计与分析间的关系就简化为:·分析部门(或人员)根据需求为设计部门量身定做各种特定产品的专用分析程序,这些程序融专家经验、自有程序、分析规范等为一体,完全专用化和自动化,一次定制,终身受益;设计部门(或人员)在针对性极强的专用程序上轻松实现设计分析-优化评价等工作;AWE多物理场协同仿真环境充分体现了 ANSYS公司“面向实实在在的工业需求,以技术为本,以优化用户产品研发流程为目标,为用户提供完整CAE解决方案”的宗旨。在AWE环境下,整个CAE应用的方式和意义都将发生革命性的变化。仿真分析的目的是优化产品性能,AWE/ DesignXplorer是基于DSDB数据库文件的参数优化工具,结合CAD系统/AGP和 Design Space/AWE进行优化:在CAD系统/AGP中第1章 ANSYS Workbench基础3·进行参数化建模,在 Design Space或AWE中进行初步的分析,并确定感兴趣的参数,在DesignXplorer中进行参数优化优化参数可以是CAD模型的几何参数、结构形式、施加的边界条件、求解得到的分析结果等,也可以是由这些参数进行数学运算后派生出来的参数,既可以进行连续性参数和离散化参数的优化,又可以进行单目标或多目标的优化,得到设计空间的三维设计响应面/二维设计曲线,并自动根据优化结果更新几何模型文件。因此,作为新一代多物理场协同CAE仿真环境,AWE以其独特的产品架构和众多支撑性产品模块已为越来越多的产品提供了非常优秀的系统级解决方案1.2 ANSYS Workbench产品设计流程和文件格式1.2.1 ANSYS Workbench产品设计流程AwE提供一个集成统一的仿真环境帮助工程人员完成产品CAE开发的全过程。在AWE环境下,典型的项目开发,包括以下模块:DesignModeler,几何建模和CAD模型导入模块;Design Simulation,结构、热和电磁有限元分析模块;Design Xplorer,最优化设计模块。AwE统一的开发环境以及具有攀升化的设计方案,帮助企业真正实现产品设计仿真到优化的协同。其中, Design Simulation与CAD系统之间可进行双向模型参数互动、可将 ANSYS嵌入CAD运行环境,使用CAD环境中的几何模型的链接,不存在模型转换失真的棘手问题。同时, Design Simulation从CAD中导入装配体时可以自动建立装配接触关系。这样,设计人员可以在 Design Simulation中进行零件以及装配体性能的初步快速分析,并确定感兴趣的区域和性能,再利用 Design Simulation中高端CAE仿真工具和疲劳分析模块一 Fatigue Module对产品强度、动力学特性以及疲劳寿命进行深入的认知,确定优化设计参数,最后在多目标优化模块一 Design Xplorer中同步优化参数,改进产品设计。软件系统的主框架如图1.2所示。ANSYS WorkbenchDesignModelerE Design Simulation Design Xplorer图1.2AWE系统框架图除了上述的主要流程模块之外,AWE还包括以下辅助模块:Engineering Data,用于设定材料和载荷加载信息;FE Modeler,用于输入来自 NASTRAN, ABAQUS,或 Design Simulation所建立的网格模型,作为 ANSYS有限元分析的输人,它也能将网格模型反演生成几何模型;ANSYS AUTODYN,爆炸、冲击等结构显式动力学分析模块。ANSYS Workbench设计、仿真与优化1.2.2文件格式AWE中涉及的主要文件的类型及格式如表1.1所示表1.1AWE中文件格式说明文件名类型说明obname, wbdbWorkbench项目数据库文件,用于管理项目中的不同类型模块文件bname agdbDesign Modeler数据库文件,用于存储几何模型信息jobname cmdbCFX- Mesh数据库文件,用于存储流体网格信息jobname dsdbDesign Simulation数据库文件,存储结构、热和电磁仿真中的所有模型信息obname, edbEngineering Data数据库文件jobname fedbFE Modeler数据库文件,用于存储从 NASTRAN或 DesignSimulation输入的网格信息jobname adANSYS AUTODYN数据库文件,用于存储显式分析软件 AUTODYN必需的信息jobname ddbDesignXplorer数据库文件,用于存储优化方程中设计参数和目标参数的关联信息13安装和起动配置1.3.1 ANSYS Workbench11.0安装安装 ANSYS Workbench1.0前需要将 Windows2000打SP2补丁( Windows XP打SP1补丁),并安装IE6.0以上。另外,系统的日期和时间,要是当前的日期和时间。具体的安装步骤如下。(1)放入安装光盘,在弹出的“ ANSYS DVD Launcher”窗口中,选择“Next”,进入下一级安装窗口,如图1.3所示。ANSYS Products 11.0for Windows 32-bitOperating SystemsANSYS图1.3 ANSYS DVD Launcher窗口1第1章 ANSYS Workbench基础(2)在弹出窗口(如图1.4)中,选择安装的产品“ ANSYS Products”,并在接下来的安装语言窗口,选择“ English”,进入下一级安装界面。ANSYS ProductsInstall ProductsANSYS AA图1.4 ANSYS DVD Launcher窗口2(3)在图1.5所示的弹出窗口中,选择“ L AGREE”后,单击“Next”,进人到下一级安装界面ANSYS需oLGRIEsiDoN et图1.5 InstallShield wizard窗口1(4)根据您的需求选择安装的路径(如图1.6),单击“Next”后进入到“ Select Installation Components"。(5)在图1.7所示的窗口中选择完毕后一直单击“Ncxt”,安装程序开始安装ANsYs11.0。(6)在图1.8所示的窗口中单击“ Finish”,完成软件安装。(7)回到步骤(2)中的“ ANSYS DVD Launcher”窗口,单击“ License Management”,出现下一提示画面(如图1.9),问是否是 license server machine,选择“是(Y)(8)出现下一提示画面(如图1.10),问是否有 license文件,选择“否(N)(9)出现下一提示画面(如图1.11),问是否继续安装,选择“是(Y)ANSYS Workbench设计、仿真与优化图1.6 Installshield wizard窗口2ANSYSwr图1.7 InstallShield Wizard窗口3ANSYS图1.8 InstallShield Wizard窗口4
    2020-12-05下载
    积分:1
  • 单相PWM整流器开环仿真Simulink模型参考(20KHz开关频率)
    单相PWM整流器开环仿真Simulink模型参考(20KHz开关频率)
    2020-11-04下载
    积分:1
  • 单相电压型PWM整流电路原理分析与仿真
    使用simulink实现的单相电压型PWM整流电路原理仿真 ,内附doc原理说明
    2020-12-08下载
    积分:1
  • MPSK信号基于高阶循环谱估计载波频率matlab的代码
    MPSK信号基于高阶循环谱估计载波频率matlab的代码
    2021-05-06下载
    积分:1
  • verilog HDL实现双线性插值视频缩放
    该文档里包含verilog语言编写的双线性插值实现图像缩放的算法
    2020-12-07下载
    积分:1
  • matlab仿真计算光纤的色散和自相位调制
    在matlab下仿真计算光纤的色散和自相位调制特性
    2020-12-05下载
    积分:1
  • linux-selinux功能及源码分析
    该书详细介绍了linux中关于selinux部分功能的实现流程和关键代码分析7.1.1.3基于创建者SID的文件系统.,,7.1.2 Gcncralizcd Sccurity Context labeling,,,,637.1.4 Mount-Point labeling667.1.5 Initial SId87.1.5.1 Initia1SID和 Initial sc的定义7.1.5.2 Initia1SID和 Initial sc的写出和解析707.1.5.3 Initia1SID和 Initia1SC的使用717.1.6进程创建的内核数拥结构的标签727.2何时需要为应用程序开发pp?●··垂·看垂723设计pp的一般过程7.4为vock程序编写v1ock.pp●垂春·垂767.4.1第一阶段:定义基本的te,fc和.if文件767.4.2第二阶段:根据 AVC Denied msg补充相应的规则807.4.3第三阶段:使用 don audit规则屏蔽与冗余操作枓关的错误信息7.4.4其他注意事项87.5为 samhain程序编写 samhain.pp..857.5.1第一阶段:定义基本的.te,,fc和.if文件事垂垂7.5.2第二阶段:根据 AVC Denied msg补充相应的规则07.5.3第三阶段:使用 don audi t规则屏蔽与冗余操作相关的错误信息927.5.4图解:使用 samhain时的 Domain transition过程春春鲁看D垂垂春,,937.6使用 SLIDE来开发pp,分析 SELinux源代码.7.7编写pp时的注意事项中垂鲁鲁··●,,,,,,,,,,,948. SELinux问题分析步骤总结.8.1排除DAC权限的问题,,,968.2检查用户当前所扮演的角色963分析 AvC Denied message: Target的标签正确吗?,8.4在系统启动过程中适时地修复错误的文件标签97应用程序的实际行为要和其pp的假设相一致,,,,988.6明确相应 domain所缺少的权限8.7其他注意事项8.7.1在 Permissive模式卜调试,998.7.2取消所有的 dontaudit规则.8.7.3当心 MLS Constraints1008.7.4检査 SeLinux- aware应用程序的配置和编译选项,.1018.7.5积极地和社区交互.1018.7.6使用 strace直接定位失败的系统调用(重要!).………1028.8 selinux问题分析过程和方法举例( Revisited),,1028.8.1实例一:用户无法在 console上正常登录-使用 strace定位失败操作1028.8.2实例二: sysadm r无法正确使用 useradd命令108SELinux开发笔记.…,,1149.1使能对/dev/ console的支持1149.1.1提出问题:20101213及之前的 epolicy缺乏对 conso1e的支持9.1.2分析问题··p9.1.3解决问题.1169.1.4测试结果1179.1.5使用 strace观察 consolo被重新打标签的细节(new),,,,1179.2 Socket labeling开发,1189.2.1提出问题: socket默认继承其创建者的SID的副作用,,,,,1189.2.2分析问题1199.2.3解决问题1199.2.4测试结果.,.1239.3给 role transition规则添加c1ass的支持,,..,,1249.3.1提出问题-当前 role transition规则只对 process类有效,,1249.3.2分析问题..,,,,,.1249.3.3解决问题D垂垂垂,,,,,1259.3.4测试结果,,,,,1319.3.5其他说明.1339.3.6经验总结●非春…1359.4增加 role attribute的攴持(new).,,,1369.4.1提出问题之一:roe- dominance规则的局限性1369.4.2提出问题之二:期望的 role attribute使用模型..1409.4.3分析问题1429.4.4解决问题D1439.4.5测试结果639.4.6一个有意思的编译问题,,,,1689.4.7有关role- types规则语法的讨论.,,.1719.5区分 tuna1e和 boolean(new).···1729.5.1提出问题无用的 tunable分支被写入 policy.X.729.5.2分析问题1739.5.3解决问题,,1749.5.4测试结果.1879.5.5其他经验总结9.N在策略中指定 newcontext的缺省设置方法(todo)1929.N.Ⅰ提出问颋- newconteκt的设置策略被硬编码到机制中19210. SeLinux内核驱动分析小记19410.1LSM核心数据结构及相应回调函数,19410.2 sELinux核心数据结构.19410.2.1 selinux对内核数据结构的扩展19410.2.1.1进程的安全属性19510.2.1.2文件和打开文件描逋符的安全属性.,,.,,,,,,..19510.2.1.3 socket的安全属性10.2.1.4文件系统超级块的安全属性1960.2,2AVC数据结构.19710.2.3內核 policy中保存TE规则的数据结构.,19910.2.4內核 policy中保存RBAC规则的数据结构.鲁鲁,,,,,20010.2.5 SeLinux规则在内核中的检查点总结(new)..,,,,,,20110.3情景分析:打开文件时的相关函数调用链20110.4通过 SEL inuxfs访问内核 Security Server,,,,,,,,,,,,,,20810.4.1/ selinux/load和1 oad policy命令一装载冰解析 policy.二进制文件20910.4.2/sc1inux/ relate1及 compute relabel命令-查询 type change规则21110.4.3/ selinux/ create及 compute create命令-查询type_ transition规则21110.4.4/ selinux/ member及 compute member命令-查询 type member规则.21210.4.5/ selinux/ access文件和 compute av命令-查询a11ow规则...21310.4.6/ selinux/user文件和 compute_user命令-查询用户登录后可能的SC21310.4.7/ selinux/ initial contexts/-查询 Initia1SI对应的安全上下文21410.4.8/ selinux/ class/-查询内核 class datum数拥结构(todo10.5情景分析: Domain transition的实现●··垂·看垂,,,,,,,,,,,,,,,,,,,,,21510.5.1 selinux setprocattr凼数-/proc/lpid/attr/“文件驱动21610.5.2 do execve的行为和相关 seLinux内核驱动垂垂看21810.6情景分析:文件系统的挂载和新文件的创建2110.6.1文件系统的挂载过程(new)..22110.6,2确定新创建文件的标签...23610.7 Context数据结构和u32sid之间的映射24110.7.1 sidtab node的定义和 sidtab的组织结构.24110.7.2 sidra_ insert函数- sidtab node的插入·,,,,,,,,,,,,,,24210.7.3 sidtab context to sid函数返回或分配sid..24310.7.4 security transition sid函数-计算新 subject/ object的sid....24410.7.5创建 context并注册到 sidtab以获得sid的时机.24910.7.6 security context to sid函数返回Sc字符对应的sid....25010.7.7 sidtab scarch corc囪数- sidtab node的查找,,,25110.7.8 security sid to context core函数-返回sid所对应的SC宇符串25210.8 Class Mapping..25410.8,1C1 ass mapping的作用..,,,,,25410.8,2 Class Mapping的创建垂垂垂·,,,,,,,,,,,,,,,,25410.8.3 Class mapping的使用-c1ass/perm内核态和用户态索引的转换.25710.8,4增加 class或者权限的方法25810.9和文件操作相关的回调数9. 1 selinux file mprotect回调函数25910.10和 AF UNIX SOCket相关的回调函数(todo),26310.11和程序执行相关的操作(todo).26410.11.1se1 inux bprm secureexec凼数-扩展 AT SECURE机制26410.11.1.1C库 AT SECURE机制介绍26410.11.1.2C库 AT SECURE机制演示26710.11.1.3 SELinux对 AT SECURE机制的扩展( Revisited).26911.用户态应用程序对 SeLinux的支持27211.11 selinux相关文件分析,27211.1.1 selinux config,c文件.,,27211.1.2 gelfilecon.c文件,,,,,27211.1.3 procattr.c文件.27211.1.4 compute relate1.c文件(访问/ selinux/ relate1)..27311.2 newrole源代码分析,27411.2.0 newrole命令的使用模型2742.1main函数7311.2.2 parse command linc arguments函数.,,,27611.2.3 relabel tty函数2761.3PAM模块分析..,27711.3.1 pam sC1inux.so作用分析(TODO27711.3.2pam1 oginuid,so作用分析,27811.3.3 pam name space.so作用分析.,27911.3.3.1多态( polyinstantiation)的作用,,,,,,,,,,,27911.3.3.2LSP对多态的配置,,,,,,,,,,,,,,28111.3.3.3 SELinux对 polyinstantiation的支持.,,,,28111.3.3.4解决在使能多态后 crond的使用间题28211.3.3.5 pam namespace,so源代码分析(IODO11.3.3.6有关 pam namespace.so的剩余问题8412. refpolicy的编译,链接,扩展,,,,,,,,,28512.1描朮标识符的数据结构8512.1.1 type datum t8512.1.2 common datum t12.1.3c1 ass datum t.,,,,,.,,,,.28612.1.4ro1 e datum t..,,,,,,曲D,.,28712.2描朮规则的数据结构..28812.2.1 AVTAB AV和 AVTAB TYPE类规则..,,,,28812.2.2 rolc transition规则●·垂,,,,,,,,,,,,,,,,,29012.3用户态 policy t数据结构分析.12.3.1 policy t数据结构综诚29012.3.2 symtab符号表.29412.3.3 avrule block t, avrule decl t FH scope stack t12.3.4 scope datum t-描迒标识符的定义者和使用者29712.3.5 scope index t-描逋一个b1ock/dec1内定义或引用的标识符.29712.3.6 cond node t-描朮一个ir- else conditiona29812.4 module的编译- checkmodu1e..30112.4.1编译过程核心数拥结构关系图30112.4.2 define policy- policy module词法分析....30212.4.3 begin optional- optional_ policy词法分析30412.4.4 declare type-type标识符的定义,,30312.4.5 require type-声明对type标识符的外部依赖31512.4.6 define te_ arab-TE规则的词法分析..31812.4.7 define role_ trans- role transition规则的词法分析32412.4.8 define conditional-if- else conditiona1的词法分析.2912.5 module的链接- semodule1ink.12.5.1链接过程核心数据结构关系图34012.5.2 symtab符号表的拷贝...,,,,,,34112.5.2.1 p types符号表的拷贝,,..34112.5.2.2所有其他标识符符号表的拷贝,,,,,,,,,,,,,,34412.5.2.3 p roles符号表的修正12.5.3 Scope符号表的拷贝34912.5.4链接过程的主要囪数调用链12.6 module的扩展- semodule_ expand37012.6.1 expand过程核心数据结构关系图..37012.6.2type的拷贝..37112.6.3 common的拷贝,,,37412.6.10 expand过程的核心函数调用链,.,,,37612.6.11展开规则的“字面”描诚- copy and expand avrule block囪数..38312.71ink和 expand过程的图解(new),,,,,,,,40012.7.1Role/ attribute标识符的1ink和 expand..…………40012.7.2 symtab的1ink和 expand,,,,,,403128规则中的m4宏定义(new)..,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,40513. seLinux的应用41013. 1 Labeled Networking (half-baked),,,,,,,,,,,,,,,,,,,,,,,41013.1.1 IPsec简介,,,,,41013.1.2 seLinux对本地网络的控制( compat-net),,,,,,。,,,,,,,41613.1.3用 Labeled ipsec实现分布式网络控制..41713.1.4 Linux內核ⅹIM相关数据结构.41813.1.5和 IPsec相关的类,权限和援囗D41813.1.6LSM中和 Labeled ipsec相关的回调函数,41913.1.6.1检查一个f1ow(发送或接收)能否使用一个SPD条目41913.1.6,2给SPD/SAD分配安全属性.,,,42113.1.6.3释放SPD/SAD中的安全属性,,,,,,,,,,,,,,,.42413.1.6.5逐包检查一个 socket能够接收一个skb42413.1.6,4获取发送方的安全上下文字符串..,,4231.7 Labeled ipsec环境的搭建.13.1.8观察 Labeled ipsec的行为43013.1.9和 Labeled ipscc相关的 SeLinux规则,432参考文献434简化 selinux操作的bash配置方法本文档各个版本的说明437注第1至5章包含自己对《 SELinux By example》一书的学习心得;第6至9章包含自己实际经验的总结第10和11章为 selinux内核和用户态源代码分析总结第12章为 refpolicy的编译过程源代码情景分析;第13章打算收录些 SeLinux在内核或者用户态的应用,比如 Labeled Networking,XACl等。l, Refpolicy有300+个p的实现,了解核心pp的实现,必须首先了解应用程序的行为以及安全目标2,阅读 sELinux- aware应用程序源代码,看如何使用 libselinux库函数,学习 sELinux用户态编程3,了解 sELinux语法,标识符的二进制表示形式,内核态和用户态的数据结构;4,学习 policy module的 compile/ expansion/1ink过程5,按照类别,逐步掌握LSM回调囪数的调用时机,所在内核子系统的原理,以及 SELinux对LSM回调函数的实现(参考《 Implementing sElinux as a lsm module》一文)6,掌握 seLinux对各个内核子系统核心数据结构的扩展7,学习XAC规范,体会如何开发 Userspace Ob、 ject Manager;8,积极阅读 Joshua,Dan等人的b1og,向前奉们学与。9,积极关注 selinux邮件列表上的问答和讨论,丰富自己的视野希望能通过自己坚持不懈的努力,证得同满的 sELinκ知识和智慧。引子1,软件的缺陷不可避免(无论过去,现在,或将来);2,没有底层操作系统的支持就无法真正实现上层软件的安全性D. Baker,《 Fortresses Built Upon Sand》操作系统中访问控制模型的演化1.1访问控制模型的概念( Reference moni tor)subjectsAccessobjectsAlertYes or No?Feference validation MechanismRuleelampcrpra吋DBVerifiableRY M由上图可见,访问控制模型由如下四部分组成1, Subjects:访间的发起者,比如系统中的进程2, Objects:被访闩的对象,比如架作系统所管理的仼何资源丶数捃(包拈进程,任意类型文件,Tc尸端口,甚至单个网络报文。总而言之,任何内核数据结构都可能成为被访问的对象)3, Rules de:规则库,在用户态实现的访问策略,定义 Object的属性并规定哪些Sub、ect可以通过什么样的方式对它进行访问;4,RVM( Reference validation mechanism):在操作系统内实现的机制,是汸问控制策略的执行者,在访问操作过程中根据规则库判断当前操作是否合法;Hinx首先需要标识访问者和被访问的对象,由下文可知相关信息保存在进程的 task struct以及其他内核数据结构中 security指针所指向的数据结构中(注意这些数据结构都是运行时动态创建的,安全属性信息来源于文件在辅存上的扩展属性,以及规则库中的 Initia1S1定义等)。白用户态定义的访问规则库指定哪些访闩老能够以何种方弌访问哪些对象,而内核屮的SεLix机制则根据当前操作的访问者和被访问对象,查询规则库得到Yes/No结论。1.2DAC( Discretionary Access Contro1)的致命伤¨ discretionary”一词的含义为“ not contro1 led bv strict rules, but decided on by someonein a position of authority”,所以DAc的本质是由文件的属主定义其它用户对该文件的许可访问方式,其“ owner-group-wor ld”模型如下:S 1s -1 /usr/bin/passwdrwsr-xr-x I rootroot 37084 2009-04-04 13: 49/usr/bin/passwd系统中所有文件属主给各自文件所定义的“ owner-group-wor d”模型的总和,即为DAC下访问规则库的实现。DAC的开发环境(相对封闭的开发社区,或大学实验室)和对软件使用环境的假设(软件没有缺陷且运行环境友好)注定了DAC存在着天生缺陷:进程和文件的安全属性都基于(且总是基于)uid/euid和gid/egid,无论进程执行什么应用程序,其uid/euid都不改变(暂不考虑 setuid类程序),无法将进程所执行程序的行为和可靠性(安全性)标识到进程的安全属性中,导致操作系统无法有针对性地对进程施加访问控制比如,用户登录 shell进程会创建子进程以执行shel1的外部命令,子进程继承父进程的uid/gid,所以无法通过uid/gid来区分父子进程,即无法区分用户人为的操作和通过程序执行的操作。比如,无法限制 passwd程序只能被用户在命令行执行,而不能被属于该用户的其它进程执行。显然,“用户(登录hc11进程)是可信的”绝对不等于“用户执行的程序(后继fork的子进程)也是可信的”。登录sh1进程的行为由用户有意识地支配,而属于该用户的进程的行为则由其执行的实际程序决定。但是程序可能冇在安全漏洞,一巨被攻击植入恶意代码,黑客将具有该用户在系统上的所有权力(比如恶意删除用户的文件,盗取uid/gid所能读取的文件的内容,执行 passwd程序修改用户的密码)另外,用户进程可以执行各种应用程序,而这些程序自身的行为丶对系统安仝性的景响都不尽相同,比如网络类应用程序更容易受到外界病毒的攻击,相应地操作系统应该对此类应用施加更为严格的访冋控制。显然无法通过进程的uid/gid来描当前进程所执行的程序的安全性,因此操作系统也无法有针对性地实施访问控制。综上所逋,仪将uid/gid来作为进程和文件的安全属性是远远不够的最后,DAC的另一个缺点是对权力的管理和划分不够细致(只有两种情况:root或non-root),无法进步细分丶限制root用户的能力。一旦euid/ egid为0的进稈被攻破,将危害整个系统的安全1.3MAC( Mandatory access Contro1)的起源针对DAC的缺点,在ⅥAC中不再由访问对象的属主定义不同用户对其的许可访问方式,而是由匿定的规则库决定。MAC最初的研究由美国军方的MLS(u1ti- Leve1 Security)应用所推动,它将访问主体和被访问对象分成不同的安全级别,严格控制信息只能从低安全级别向高安全级别流动:低安全级别的丰体只能向高安全性的数捃对象中追加新的数据,并∏禁上读取;高安全级别的主体能够读取低安全级别的数据,并且禁止任何形式的写入(即“ no read up, no write down”)ⅥS只定位于数据保密性而并不关心数据完整性和最小权能原则( east, Privilege),以及对进程的能力进行分类。后来的FASK安全系统模型着眼于解决这些不足,而 SELinux则是FASK在 Linux内核中的实现1.4 Selinux的TE( Type Enforcement)模型SELinux作为MAC的一和实现,通过中央规则库( policy.x,二进制数据文件)给所有进程丶所有文件内核数据结构定义各自的安全标识(标签,1abel/type),明碓定义被访问对象所支持的访问方式,并规定进程标签对被访问对象的合法的访问方式。在配置 SELinux时给整个文件系统上的所有文件设置标签,在系统启动过程中init进程经由 selinux接口装载 policy.X到內核空间,由內核中的 SecuritvServer在处理用户态系统调用时实时査询(注,这里所说的“ Security server”,即为 sELinux内核驱动中定义的各种数据结构,比如 sistah, policy, AVC cache,以及在 services.c文件中定义的各种以“ security”开头的函数)
    2020-12-04下载
    积分:1
  • 696516资源总数
  • 106432会员总数
  • 11今日下载