保护你的隐私，五种控制Android应用的权限的方法

保护你的隐私，五种控制Android应用的权限的方法:

　　这篇文章目的在于介绍Android系统上控制权限的方法，读者只要使用过Android，或是对智能机平台有所了解，就能看懂，不需要专门的编程知识。

　　1 为什么Android总是事无巨细地告诉你应用索取的每一项权限？

　　相比Apple，Microsoft严格控制生态系统(从苹果给开发者的"App Store Guideline"可见一斑)，只允许通过官方应用商店安装应用，并对每份上传进行仔细地审查而言，Android的开放就意味着，Google需要向用户提供一系列用于为自己负责的流程、工具。所以在安装应用前，Android总是要事无巨细地告诉你，应用肯需要控制什么权限。

　　同样，开发者也制作了一系列易用的工具，用以鉴别可疑的应用程序，或是控制权限。

图1 Android 官方市场会强制提醒用

　　Andoird哪里开放了？

　　在Android中，用户能自由从本地安装应用，自由地对SD卡进行操作，自由选择应用市场。

　　如果愿意放弃保修，用户还能轻易地实行root，解锁基带(baseband)。只有一些产品会严密地锁定bootloader(如摩托罗拉)。

　　最重要的是，因为ASOP(Android源代码开放计划)的存在，绝大部分的Android代码都是开源的，开发者可以由此对Android系统进行深入的修改，甚至可以自行编写一个符合Android规范的系统实例(如Cyanogen Mod)。正是因为ASOP，这篇文章才可能介绍多达5种原理不同的权限控制方法。

图2 Android开源计划的标志

　　开放的风险

　　不考虑Symbian，Windows Phone 6.5(及以下)平台，那么几乎所有的智能手机病毒都是Android平台的，甚至官方Android Market也闹过几次乌龙。在国内水货横行的市场，情况更是火上浇油，不法业者可以在手机的ROM，甚至是bootloader中做好手脚，让用户有病无法医。

　　在Android中，用户可以允许系统安装来自"未知源"(也就是非Google官方的，或手机预置市场的)应用程序。于是，移动平台最重要的门神------数字签名就被绕过了。

图3 Android 允许未知安装未知来源的应用程

　　出于Android的开放性，也有不允许"未知源"的反例：亚马逊的Kindle Fire平板使用了深度定制的Android，它只允许安装来自亚马逊官方商店的应用程序。

图4 亚马逊的 Kindle Fire 仅允许通过自带的市场安装应用

　　2 Android有哪些"权限"

　　首先需要明确一下Android中的种种"权限"。Android是在Linux内核上建立一个硬件抽象层(Android HAL)，通过Dalvik以及各种库来执行android应用的。在手机启动时，首先需要由Bootloader(HTC手机上称作Hboot)引导Linux及手机上各个硬件设备的驱动程序，之后才启动Android系统。所以其实我们会涉及到四种不同涵义的权限：

　　Android权限(Permission)

　　这指Android中的一系列"Android.Permission.*"对象，是本文的中心内容。

　　Google在Android框架内把各种对象(包括设备上的各类数据，传感器，拨打电话，发送信息，控制别的应用程序等)的访问权限进行了详细的划分，列出了约一百条"Android.Permission"。应用程序在运行前必须向Android系统声明它将会用到的权限，否则Android将会拒绝该应用程序访问通过该"Permission"许可的内容。

　　比方说，搜狗输入法提供了一个智能通讯录的功能，用户可以在输入联系人拼音的前几个字符，或首字母，输入法就能自动呈现相关联系人的名字。为了实现这个功能，输入法必须声明它需要读取手机中联系人的能力，也就是在相关代码中加上声明"android.permission.READ_CONTACTS"对象。

图5 搜狗输入法的智能联系人功能

　　原生Android只提供了对"一刀切"式的管理，要么同意使用，否则就根本就不安装应用程序。当用户遇到希望使用程序的同时，又想禁止部分Permission的场合，他就无路可走。

　　于是，不少开发者就捣鼓出了"第三条道路"；可惜的是，没有一种方法能同时做到既不需要将手机固件Root，又完全不涉及对原始应用程序进行反向工程的方法。

　　Root

　　Root指获得Android所在的Linux系统的Root(根)权限，有了根权限，你才能对Linux做出任意的修改。iOS中的越狱(Jailbreak) 相当于获得iOS系统的Root权限(iOS是一种类Unix系统，和Linux都使用Root的概念)。在已Root的设备中，通常都是使用一个叫"Superuser"(简称SU)的应用程序来向许可的程序授以Root权限。

　　Bootloader的解锁(Unlock)

　　利用数字签名，Bootloader可以限定只有正确签名的系统可以被引导。在修改固件以获得Root以前，解锁Bootloader通常是必须的。安装第三方修改、编译的固件也需要解锁Bootloader。

　　基带(Radio)解锁

　　在Android系统中，基带是上层软件与手机中无线设备(手机网络，Wi-Fi，蓝牙等)的驱动程序之间的中介。国外的网络运营商很喜欢锁定基带，从而保证用户只能使用运营商自己指定的sim卡。在我国，锁定基带是非法的，手机制造商、网络运营商也不可以通过锁定基带的方法对待违约客户。iOS的"解锁"就是解锁iOS中的基带软件。

　　为什么要控制Android权限

　　鱼和熊掌不可兼得，Android的世界有很多自由，坏人也能自由地做坏事。它的生态系统很强调自主：用户可以自主地减小风险，仅使用官方市场的应用程序，也可以自主地解除安全限制，从而获得更多自由。因此，在遇到坏事的时候，用户也不得不自主一下：

　　1， 抵制不道德，乃至非法行为

　　几乎所有的Android安全软件都能对来电、信息进行控制，以减少骚扰。

　　另一方面，很多应用都会要求它们实际功能以外的权限，表现在非(主动)告知地搜集设备序列号，位置信息，诱使用户默认地上传联系人列表等方面。

　　更坏一点的应用程序，则会踏入犯罪的范畴，比如能偷偷发出扣费信息，或是作为黑客的偷窥工具。

　　2， 减少恶意软件的损害

　　恶意软件即便潜伏成功，也难以获得权限，从而减少损失。

　　3， 用户有权自主地在抑制应用程序的部分权限时，继续使用该应用程序，而只承担由于自行设置不当而带来的后果。

　　用户拥有设备的所有权，因此有权自主控制设备上的内容、传感器等对象的访问；同时有权(不)运行，(不)编译设备上的应用程序。

　　大多数应用程序在运行时，并未达成主动告知的义务，是失误；然而即使主动告知，用户还是可以不理会。

　　为什么Android官方市场的强制提醒权限的行为不属于主动告知：

　　通过Android官方市场，"打包安装器"安装应用程序时，所显示的"权限"仅是在安装包内AndroidManifest.xml声明的值，而非应用程序实际上会调用的内容。该值仅用来表明Android系统能向应用授予的最大可能的权限。即便一个"Hello World"式的应用程序，也可以在AndroidManifest.xml中声明所有可能的Android Permission。

　　这就是说，在AndroidManifest.xml中声明的值与应用程序实际调用的权限有关联，但不等同，且这种提示是由Android系统负责实施的强制行为。

　　正确的理解是："应用程序(被迫地)让Android系统告知用户，它在AndroidManifest.xml中所声明的事项。"

　　这意味着应用程序在使用重要权限前，依然需要自行、主动地通知用户相关事宜。

图6 应用程序须要AndroidManifest.xml中声明调用到的权限

　　然而，即便只是让一半的应用程序达到以上的标准，也是不可能的。应用程序需要通过收集用户信息，程序的错误日志。从而统计用户的喜好，改进程序。另一方面，这也是发送精确广告但不追溯到用户身份信息的方式，这一点对于免费应用而言，是极其重要的。我们之所以能知道不同型号手机的占有率，应用软件的流行度，是与这样的统计不可分离的。

　　一旦每个应用程序都专业地主动发出提醒，不专业的用户(大多数用户都是不专业的)通常会将之视为如同海啸警报一般的危机。

　　这么做对谁都没有好处------用户方的隐私权是毋庸置疑的，然而应用程序方面的获取信息记录的需求也是无可阻挡的。如果每个用户都打算阻止，只会落得被迫接受不平等条约的下场，在温饱以前，不会有人考虑小康的问题。

　　于是，现状就变得有趣：用户人享受着相同的服务；其中大部分用户出于不知情/好意，默默地向开发者、广告商提供了信息，剩下的少数用户则能阻断这种劳务。而作为维持Android平台的信息商人Google，只确保在它的地盘里，不会发生触碰底线的事情。

　　一句话总结：

　　设备是我的，不管你怎么说，反正我说了算，但我说的话大多是不算数的。

　　3 权限控制的方法

　　这里开始介绍各种控制Android权限的办法。可惜的是，几乎所有的手段都需要对设备进行Root，如果不这么做，则需要付出不小代价。

　　App Shield(国内常见的名字:权限修改器)

　　它是一个需要付费的Android应用，其原理是修改应用程序的apk安装包，删除其中AndroidManifest.xml文件内，用于声明权限的对应"Android.Permission.*"条目，然后再用一个公开的证书对安装包重新签名(需要允许"未知源")，这样一来，应用程序就不会向系统申请原先所需的权限。当应用运行至相应的流程时，系统将直接拒绝，从而达到用户控制权限的目的。

　　对于已安装的应用，AppShield也会按照同样方法制作好apk安装包，然后让用户先卸载原始的应用，再安装调整过的应用。除了该应用数字签名外，用户可以随时通过执行同样的流程，将吊销的权限恢复。

图7 AppShield

　　Apk文件的结构

　　Android应用都是打包成以.apk扩展名结尾，实际上是zip的文件格式。

　　一个合法的apk至少需要这些成分：

　　根目录下的"AndroidManifest.xml"文件，用以向Android系统声明所需Android权限等运行应用所需的条件。

　　根目录下的classes.dex(dex指Dalvik Exceptionable)，应用(application)本身的可执行文件(Dalvik字节码) 。

　　根目录下的res目录，包含应用的界面设定。(如果仅是一个后台执行的"service"对象，则不必需)

　　Apk根目录下的META-INF目录也是必须的，它用以存放应用作者的公钥证书与应用的数字签名。

　　当应用被安装后，这个apk文件会原封不动地移至设备的data/app目录下，实际运行的，则是Dalvik将其中Classes.dex进行编译后的Classes.odex(存放在Dalvik缓存中，刷机时的'cache wipe就是清除Dalvik的odex文件缓存')。

　　优点：

　　完全不需要Root，适用于所有版本的Android设备。不会损坏系统，可以吊销任意一项Android权限。

　　问题：

　　1，需要重新安装应用，该行为可能会丢失应用的配置、历史记录。

　　2，执行权限吊销的应用的数字签名会被更改，无法直接更新。对于那些设计不良(没有意料到'不声明权限'情况的)，或有额外自校验的应用，可能会无法运行。

　　3，无法用于设备上的预装应用，除非制造商好心地将该应用设置为"可以删除"的状态。

　　4，这个方法修改了apk包中的内容------尽管实际上AndroidManifest.xml和数字签名并不算是应用程序的本身，但修改它们可能引发著作权的问题。

　　5，需要开启"未知源"。

　　6，这是一个收费应用。

　　CyanogenMod 7.1(及以上版本)

　　Cyanogenmod是一款著名的第三方编写的开源Android ROM。

　　CM7.1加入了控制权限的开关，官方的名称是"Permission Revoking"，任何非系统/保护应用在安装后，可直接吊销任意一项权限，其效果等价于直接删除apk包中AndroidManifest.xml的对应条目，但不会引发自校验的问题。CM的权限工具的作用等同于AppShield，无非是在Android自身的权限系统中添加了一个开关。

图8 Cyanogen Mod 7.1中的权限吊销(Permission Revoking)设定

　　优点：

　　免费，使用简便，可随时，任意地吊销、恢复非预装应用的任意一项权限；不存在数字签名的问题，因而不影响使用自校验的应用程序。

　　问题：

　　此功能仅在Cyanogen Mod 7.1及以上版本提供，无法用于其它rom。因为是由Android系统出面吊销权限，其实现原理与App Shield完全相同，同样的，应用程序会因为设计不良而出现崩溃。

　　Permission Denied

　　这是可以吊销任意Android应用(注意，不当地吊销系统应用的权限可能会导致手机固件损坏，无法启动)的任意权限，对权限的修改在重启后生效。

　　实现原理应该与Cyanogen Mod 7.1+完全相同，适用于任何已经Root的系统，因为一般的Android系统虽然事实上支持权限吊销，但没有像Cyanogen Mod那样放置接口，因此需要重启后才能应用权限配置。同样也有系统出面拒绝权限而导致的崩溃现象。

图9 Permission Denied免费版吊销应用程序权限的场景

　　优点：

　　效果与Cyanogen Mod中的权限吊销效果一致，且可吊销系统应用的权限。同时提供了免费与收费版本，免费版并没有基本功能的缺失。适用于所有版本号不低于1.6的Android设备。

　　问题：

　　调整后的权限需要重启才能生效。设计不良的应用会崩溃。不恰当的权限修改会损坏系统，导致无法开机。

　　PDroid

　　PDroid实际上是一个Android内核补丁加上一个用于管理的外部应用。补丁需要在Recover环境中刷入系统，也可以由开发者自行移植入系统。该软件在Android ASOP 2.3.4代码基础上开发，仅适用于没有改动内核的Android 2.3系统，目前还未支持Android 4。

图10 PDroid的界面

　　为了避免Cyanogen Mod 7.1+权限吊销(Permission revoking)导致的崩溃问题，以及后台服务(如LBE，QQ手机管家等，PDroid的作者认为通过后台服务拦截权限并不是好办法)，PDroid并不阻止应用程序声明权限，但会在其实际索取相关信息时，予以阻止。通俗地说，就是签署协议但不执行。在PDroid的用户界面，用户能随时精确地控制涉及隐私的各项权限。对于某些内容，除了阻止外，用户还可以伪造一个随机或指定的数据。

　　可控制的内容包括：

　　IMEI(可伪造)

　　IMSI(可伪造)

　　SIM卡序列号(可伪造)

　　手机号码(可伪造)

　　来，去电号码

　　SIM卡信息

　　当前蜂窝网络信息

　　(以上七者均来自Android.Permission.READ_PHONE_STATE)

　　GPS定位信息 (可伪造，来自Android.Permission.FINE_LOCATION)

　　基站定位 (可伪造，来自Android.Permission.COARSE_LOCATION)

　　系统自带浏览器的历史，书签(Android.Permission.BOOKMARKS)

　　联系人 (android.permission.READ_CONTACTS)

　　通话记录 (android.permission.READ_CONTACTS)

　　系统日志 (android.permission.READ_LOGS)

　　当前账户列表 (android.permission.GET_ACCOUNTS)

　　当前账户的授权码 (android.permission.USE_CREDENTIALS)

　　短信，彩信 (可能与这5个权限有关)

　　　　　　　　　　android.permission.READ_SMS

　　　　　　　　　　android.permission.RECEIVE_SMS

　　　　　　　　　　android.permission.SEND_SMS

　　　　　　　　　　android.permission.WRITE_SMS

　　　　　　　　　　android.permission.RECEIVE_MMS

　　日历 android.permission.READ_CALENDAR

　　PDroid的内核补丁并不通用，每一个Rom都需要特定的补丁。开发者除了提供了几个特定机型下Cyanogen Mod，HTC Sense修改版ROM的专用补丁外，还推出了一个补丁生成工具(PDroid Patcher)，用户可以给自己的ROM生成专用的内核补丁。使用该Patcher需要安装JDK(java Development Kit)。

　　优点：

　　PDroid避免了通过Android系统进行权限吊销的导致的潜在崩溃问题，也不需要后台服务。对隐私信息的控制是最精细的。尽管设备必须Root，但应用本身不需要Root权限。

　　问题：

　　安装过程是最繁琐，最不可靠的，容易导致ROM损坏，适用范围也小，需要用户有相当的技能(能安装JDK，会刷机)才可使用；只提供对隐私有关权限的控制，不提供网络访问，的控制。以这些为代价，它几乎没有其它缺点。

　　LBE安全大师

　　实际上最常用的是以LBE为代表的通过一个Root权限的后台服务来拦截相关行为的工具。除了LBE外，还有QQ手机管家等应用。这里以LBE安全大师为例介绍。

图11 LBE安全大师

　　LBE是国内一个叫"LBE安全小组"开发的工具，支持Android2.0～4.0。它的核心功能是像杀毒软件一般，通过一个需要Root权限的后台服务，劫持所有调用权限的行为，并放行用户许可的部分(其官方宣传为'API级别拦截')。它和PDroid一样几乎不会引发应用程序崩溃，它支持拦截几个涉及用户的关键权限(LBE手机管家3.1/3.2)：

　　读取短信 (android.permission.READ_CONTACTS)

　　联系人记录 (android.permission.READ_CONTACTS)

　　通话记录 (android.permission.READ_CONTACTS)

　　定位 (Android.Permission.COARSE_LOCATION

　　　　　　　　Android.Permission.FINE_LOCATION)

　　手机识别码 (与Android.Permission.READ_PHONE_STATE有关)

　　通话状态 (与Android.Permission.READ_PHONE_STATE有关)

　　发送短信(具体原理不明，同样类似于禁止这五个权限

　　　　　　　　android.permission.READ_SMS

　　　　　　　　android.permission.RECEIVE_SMS

　　　　　　　　android.permission.SEND_SMS

　　　　　　　　android.permission.WRITE_SMS

　　　　　　　　android.permission.RECEIVE_MMS)

　　拨打电话 (android.permission.CALL_PHONE)

　　通话监听 (android.permission.PROCESS_OUTGOING_CALLS)

　　除此以外，LBE还可以分别控制应用在Wifi，手机网络的联网权限，其原理是依靠IPtables防火墙，而非通过Android的"Internet"权限。

　　此外LBE手机管家还提供基于智能内容审查的短信拦截、来电归属地显示，以及禁用系统(保护)应用，进程管理，杀毒等功能。

　　LBE提供两个版本，一个叫"LBE安全大师"，是一个全面的手机管家类应用，更新比较频繁，另一个版本(LBE手机隐私卫士，LBE Security lite)仅提供权限方面的管理。

　　考虑到主要市场在国内，LBE的发行策略看上去有些奇怪，它在Google的官方市场并不发行最新版。通常只能只能在LBE的官方网页，以及国内的应用市场获得最新版本。

　　优点：

　　使用非常简单，功能强大而全面，风险很小，可以控制系统应用。适用范围广，有很多替代产品。

　　问题：

　　需要后台服务 (尽管蚕豆网有个评测，认为它对能耗几乎没有影响)，不能控制所有的Android权限。

　　4 自启动的控制

　　Android对后台服务有着最好的支持。

　　在Android中可以自由地开发一种称为'Service'的后台运行的对象，加上没有苹果公司对应用程序的严格限制。诸如QQ挂机，即时调用第三方应用程序之类的形式都可以轻易实现。

　　为了全面支持后台服务，也为了适应移动设备资源紧张，不得不经常清理内存的问题，应用可在系统中设置触发器，当系统发生了某个特定特定事件时(系统启动，拨打电话，收发信息，安装、卸载应用，插上电源等，或应用程序自行定义的事件)，就会触发启动应用程序。

　　AutoStarts 自启动管理

　　AutoStarts是一个收费应用，通过它，用户能了解系统中每一项程序会在什么场合下被触发运行。如果提供Root权限，则还能禁止这样的行为。

　　这里以Google Maps应用6.2版为例。默认情况下，这款应用总是会保持后台运行，并每小时向Google发送一次当前用户的位置信息。为了阻止这样的行为，需要联合使用AutoStarts与任意一款进程管理应用：在AutoStarts中，阻止Google Maps的自行启动(如图)，在每次使用完后，把Google Maps的进程杀掉。

图12 AutoStarts可以对自启动项目进行修改

　　5 其他

　　Root带来的风险

　　有一个钻牛角尖的说法认为，一旦对设备进行了Root，便无安全一说，只要恶意程序一旦偷偷获得Root级别，一切都是空谈。

　　这种说法之所以钻牛角尖，是因为：一方面Android中的Root权限通常都是需要用户通过Superuser应用进行授权的，这已经够用，虽然不能指望Superuser无懈可击；另一方面，控制Android权限主要是为了让应用程序在"灰色地带"的行为收敛一些，它们实际显然不是病毒等犯罪软件。

　　著作权的问题 (作者不是法律方面的专家，以下言论仅供参考)

　　我们知道，Android中的应用程序是基于Java语言编写的。而为了达到跨平台的目的，Java软件是以字节码(或叫中间代码，bytecode)，而非计算机能直接执行的机器码(Machine Code，有时也叫作Binary)的形式存在。因此执行Java软件时，需要一个Java虚拟机(Android系统中的Java虚拟机就是Dalvik)负责解释运行，有的时候，虚拟机还会通过即时编译(JIT)的方法将字节码编译为机器码后再运行，以提高程序的执行效率。

　　这就出现一个很有趣的现象：

　　除非另行规定，作为设备的拥有者，用户总是可以自行决定如何使用软件，能自行决定程序能否访问用户自己的计算机(移动设备亦然)里面的各个内容、对象。

　　由此衍生出，在需要对代码编译、解释的场合，用户也能通过对编译器(解释器)的干预，来影响代码的执行效果。在Android中，用户还可以在Dalvik解释、编译的时候动手。

　　这是因为，著作权仅保护了软件代码不受到非授权的反向工程，未授权传播等侵犯。另一方面，对于Android上的Java，网页中的javascript程序，赋予用户解释、编译的权利是程序能执行的先决条件；同时，软件发行者发通常也会主动提出放弃这种权利(表现为'软件按原样提供'、'不对使用软件造成的后果负责'等条目)

　　在编译、解释的过程中，需要通过汇编(Assemble)，连接(Link)等方法将编译好的对象(Object)、方法(Function)联系起来。默认情况下，这些行为是由原始的代码(源代码、中间代码)与编译器(解释器)决定的，但是用户可以通过制约编译器(解释器)的设置，从而影响到最终代码。这么做是没有问题的。

　　还有一种，应用程序在安装后，会在系统中产生一些缓存，或注册一些信息。当其中的内容有关用户数据时，读取或修改它们也是没有问题的。这就是所谓"只要是你的东西总是你的"；也是Cyanogen Mod、Permission Denied不会涉及版权问题的原因所在。

　　总之，一个Android应用之所以能运行的前提是：

　　1，首先，用户允许使用这个应用

　　这也可以理解成：用户安装了应用(以及因此设定的后台对象)，购买了预装应用的手机。这一点即不影响应用程序的主动通知义务，也不影响用户事后的干预。

　　2，接下来，用户允许Dalvik对该应用使用"解释"，"JIT"的方法，从而该应用程序得以执行。

　　3，用户随时可以对该应用作出任意不违反版权的干预。

　　所以，在没有另行规定的前提下，用户总是可以自行决定，通过给应用程序分配自定义的权限；或是在应用程序调取内容，对象时予以阻断。同时，用户也需要自行承担因不当操作产生的后果。

　　附录:

　　1、 数字签名

　　数字签名是一种使用了公钥加密领域的技术实现，用于鉴别数字信息的方法。一套数字签名通常定义两种互补的运算，一个用于签名，另一个用于验证。数字签名可以轻易地验证完整性(正确性)，合法签署的数字签名具有不可否认性。 (摘录自维基百科"数字签名"条目，有修改)

　　2、 版权声明

　　文章中引用的图标，图片或图片的部分，以及部分文字的引用，仅出于合理使用的目的，可能是持有人版权所有的。

　　3、 一些行为的说明

　　不道德行为

　　应用程序在启动时，或在主动告知以前，试图索取、收集电话号码、邮箱地址、位置信息等与个人身份直接关联的内容。如果是与个人关联，但不能直接联系到个人信息的IMEI等设备、SIM卡的串号，则稍微好一些。

　　附图1，不道德的应用程序在启动的第一时间就试图获取隐私信息

(新浪微博2.8)，无论用户是否绑定了手机，应用都会第一时间记录当前手机的号码

(UC浏览器，快拍二维码)，应用总是会不主动通知地记录设备的位置信息

　　没有实行主动通知的例子

附图2 这个应用程序在第一次启动时便开始收集位置信息，用户需要切换六次屏幕才能看到有关位置信息的提示。这项提示还有意忽略应用程序本身就会记录用户位置信息，即便用户并不使用需要位置信息的服务

　　主动通知的例子

附图3 主动通知就是在第一屏的醒目处，或用醒目的对比色等强调方式进行通告

　　来源：fcerebel投稿。

评论《保护你的隐私，五种控制Android应用的权限的方法》的内容...

相关文章:

• 手机浏览器HTML5跑分完全调查
• 我的iPhone桌面
• 给智能手机和平板用户新手的三个建议
• 同为Android手机，为何HTC拼不过三星

微博：新浪微博 - 腾讯微博
QQ群：186784064
月光博客投稿信箱：williamlong.info(at)gmail.com
Created by William Long www.williamlong.info

学习Guice

单元测试＝》接口依赖＝》Factory＝》依赖注入

有时间深入研究一下Guice，算是工作学习两不误。

一点点LLVM

今天花了些时间仔细地学习了一些LLVM，很悲剧的事情是虽然LLVM异常强大，但实在资料缺乏，而且接口改动频繁，网上大多数的简介对于LLVM 3.0都不work了（比如http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/）

最好的入门资料还是自带的sample，都是可以用的;-)今天看的第一个sample就是鼎鼎大名的BrainF语言，着实BT啊。但看着很neat的几百行代码就能把这么BT的东西变成native code，还是很爽的。

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

这一段运行出来就是打印Hello World，好吧，我hold不住了---

客观说，LLVM官网上还是有些不错的资料的，比如LLVM Tutorial，非常适合入门。当然它全是hard-code的lex和parser，如果用flex/bison应该更好些，这个应该可以借鉴Loren Segal的做法，用flex做lexical scan，用bison做semantic parse和AST生成，最后再在AST上利用LLVM做code generation应该是更靠谱的做法。

简单玩了以后，虽然大概知道了LLVM的强大，感觉主要应该就是在于JIT和code generation，以及相应的optimization，cross-platform的native code generation应该也是一个亮点，所以应该是自己写compiler的人很喜欢的东东，但不知道是否能够对code generation以及optimization做精细控制，否则我估计大多数compiler还是会自己做generation，毕竟可控性更强，至少我看到的目前一些compiler，包括比较新的Go，都没有使用LLVM来进行code generation。所以难道LLVM只是给compiler外行们玩玩的toy？

我想肯定不是这样咯，我觉得它可能最大的创新还是在于LLVM IR中间语言的引入，在project built with LLVM里看到一个很好玩的项目：Emscripten，它是利用LLVM做backend把LLVM IR翻译成javascript，这又有什么用呢？好吧，看看这个网站。以后神马语言都能转成javascript放在web上跑鸟。

最后，一个相对比较全面的学习用LLVM写compiler的网站：http://staff.polito.it/silvano.rivoira/HowToWriteYourOwnCompiler.htm，虽然不保证up-to-date，但对于系统地学习一下怎么做个OO的language应该是有帮助的，我也正在看ing。

学习LLVM

记录下

Blogger增加代码高亮

Blogger默认竟然不支持代码高亮～～～，解决方案参考这里。

blog迁移成功

今天折腾Blog迁移，杯具的Micolog只能导出WordPress格式，而且导出的WordPress格式又似乎不标准，用网上的转换工具也没能转成Atom格式给Blogger（貌似因为时间格式的问题，虽然也可以尝试预处理一下再转换，但既然要处理，为啥不彻底点呢？）

一开始的思路和转换工具一样，也是想自己写个脚本转换WordPress schema成Atom schema，可是很杯具的总是失败，Blogger导入时也没提示，不知schema的什么地方不符合标准～～～

于是开始研究Atom schema，洗具的地方在于伟大的G公司给我们提供了详细的描述：http://code.google.com/apis/blogger/docs/2.0/developers_guide_protocol.html
更强大之处在于这个spec的若干种语言的实现都提供了：http://code.google.com/apis/blogger/docs/1.0/developers_guide.html，虽然python只是提供了1.0的spec，但于我已经足够了～～～

于是，几行代码就搞定了迁移：

import sys, os
from xml.dom import minidom
import gdata.blogger.client
import gdata.client
import gdata.data
import atom.data

def usage(cmd):
 print "Usage: %s account pwd in_file\n" % cmd
 sys.exit(-1)

def get_simple_node_value(node):
 for subnode in node.childNodes:
  if subnode.nodeType in (node.TEXT_NODE, node.CDATA_SECTION_NODE):
   return subnode.data

def handle(account, pwd, in_file):
 client = gdata.blogger.client.BloggerClient()
 client.ClientLogin(email = account,
  password = pwd,
  service = 'blogger',
  source = 'Blogger_Importer-0.1')
 feed = client.get_blogs()
 blog_id = feed.entry[0].get_blog_id()

 in_dom = minidom.parse(in_file)
 in_root = in_dom.documentElement

 items = in_root.getElementsByTagName("item")
 for item in items:
  title = get_simple_node_value(item.getElementsByTagName("title")[0])
  content = get_simple_node_value(item.getElementsByTagName("content:encoded")[0])
  pub_date = get_simple_node_value(item.getElementsByTagName("pubDate")[0])
  pub_date = pub_date.split(".")[0]

  print("Importing: %s ...\n" % title)

  client.add_post(blog_id, title, content, draft = True)

if __name__ == '__main__':
 if len(sys.argv) != 4:
  usage(sys.argv[0])
 
 handle(sys.argv[1], sys.argv[2], sys.argv[3])

另，gdata除了可以用来操作Blogger外，若干Google的service都可以操作（参考这里）：

• Google Analytics
• Blogger
• Contacts
• Google Calendar
• Google Documents List
• Google Apps Provisioning
• Issue Tracker
• Google Sites
• Google Maps
• Picasa Web Albums
• Google Spreadsheets
• Google Webmaster Tools
• YouTube

用python写firefox extension

Technorati 标签: firefox,extension,python

直接用javascript写复杂的firefox extension简直是个梦魇，而且performance也会有很多问题，还有一堆限制（同源…），而用C/C++写XPCOM又太大材小用，很不适合于prototype开发。
于是想找找直接用python来写logic的firefox extension，于是就找到了pyxpcomext
其实它也是基于PyXPCOM的，参见说明：
Why do this?

• It gives the power of Python to Mozilla extension developers
• Easy to setup multi-threaded tasks
• Rapidly build cross platform extensions, no compilation issues!
• Great base of core library functionality
• Not limited to JavaScript
• Provides a Python GUI toolkit to build applications (XULRunner)

How does it all work?

• The Python extension is download and installed into a Mozilla application as a regular extension
• Upon starting of the application, the extension is registered, and loads the internal dynamic linked libraries (python, pyxpcom and pydom)
• Additional extension directories are then checked to see if there are any extensions using pyxpcom that need to be registered (and appropriately registers them)
• The internal Python path (sys.path) is updated to reflect any "pylib" directories found in the installed extensions

OK，本着庖丁解牛的精神，这里给出一个step by step的python extension

必备

---

首先要做firefox extension，当然得有firefox咯（废话，这里使用ff 3.6），要做xpi当然也得有zip工具了，linux下这不是问题，win上可以去找UnxTools，或者也可以使用ff的Extension Developer。
至于像FireBug，Explore Chrome，Javascript Debugger等等，就看你的心情咯～～～
其次，既然要PyXPCOM，装pyxpcomext先，这个是平台相关的，win/lnx会有不同的xpi：
http://pyxpcomext.mozdev.org/downloads.html
还有，既然俺们好歹也算是个XPCOM，总得搞个XulRunner-SDK/Gecko-SDK玩玩啊，其实主要我们也只是用它帮我们compile一下idl～～～

动工

---

如果有firefox extension开发经验，到这一步已经很简单了～～～
首先先做个简单的框架，把下面几个文件按部就班找个sample抄一下：

chrome.manifest

install.rdf

content/

    overlay.xul

    overlay.js

components/

然后定义IDL（components/pyIDemo.idl）

#include "nsISupports.idl"      
#include "nsIVariant.idl"

[scriptable, uuid(2B3D3376-3312-4a2d-8A1E-C93AAFBC8EF7)]      
interface pyIDemo: nsISupports {       
    // attributes, constants, methods, ...       
    nsIVariant doPythonCmd(in wstring code);       
};

写python的实现（components/pyDemo.py）

import os      
import sys       
import time       
import traceback       
from cStringIO import StringIO

from xpcom import components, ServerException, nsError      
from xpcom.server import WrapObject

class pyDemo:      
    _com_interfaces_ = [components.interfaces.pyIDemo]       
    _reg_clsid_ = "{ED590407-D31B-4076-8D3C-3AFA999960A8}"       
    _reg_contractid_ = "@zouf.trendmicro.com.cn/pyDemo;1"       
    _reg_desc_ = "Python Plugin Demo"

    pyshellGlobals = {      
        # Give away some free items...       
        "os": os,       
        "sys": sys,       
        "time": time,       
        # And xpcom accessors.       
        "components": components,       
        "Components": components       
    }

    def __init__(self):      
        pass

    def doPythonCmd(self, code):      
        # Ensure the code ends with an empty newline       
        try:       
            try:       
                result = code + 'Hello'       
                try:       
                    # See if the result can be turned into an xpcom object       
                    return WrapObject(result, components.interfaces.nsIVariant)       
                except ValueError:       
                    # else, we'll just return a string representation       
                    return repr(result)       
            except SyntaxError:       
                return self._exec_code_and_get_output(code)       
        except Exception, e:       
            # Format the exception, removing the exec/eval sections.       
            exc_tb = traceback.format_exception(sys.exc_type, sys.exc_value, sys.exc_traceback)       
            return "".join(exc_tb[:1] + exc_tb[3:])

这个python就太简单不过了，只是在输入的wstring上在加个Hello把它返回～～～
好，实质内容都有了，下一步就是让javascript做个中转器，帮UI来调用python了，这个我们把它放在overlay.js里：

function do_cmd() {      
    _pySvc = Components.classes["@zouf.trendmicro.com.cn/pyDemo;1"].       
                    getService(Components.interfaces.pyIDemo);       
    alert(_pySvc.doPythonCmd('abc'));       
}

OK，基本上到这一步你的coding工作就完成了，当然实际上在这一步你会花费数百倍的精力去写你的python logic～～～
下一步就是收尾，打包，一下的简单批处理可以帮忙（build.cmd）

@echo off

SET XUL_PATH=D:\projects\xulrunner-sdk      
SET PATH=%XUL_PATH%\bin;%PATH%

xpidl -I %XUL_PATH%\idl -I components -o components/pyIDemo -m typelib components/pyIDemo.idl

zip pydemo.xpi install.rdf chrome.manifest pydemo.jar -r components -r content -r locale

它干的活也很干净，只是编译IDL，zip打包，出XPI，大功告成～～～
最后把出来的xpi拖到你的ff里试试吧，看看能不能出结果？
#END#

Firefox Extension: Hook

 

Technorati 标签: firefox,extension,hook

URL Hook

---

有时需要在Firefox加载URL之前hook住URL，对URL做些check，比如判定URL是否为phishing site，是否需要block等～～～

var myListener =
{
    QueryInterface: function(iid)
    {
        if (iid.equals(Components.interfaces.nsIURIContentListener) ||
            iid.equals(Components.interfaces.nsISupportsWeakReference) ||
            iid.equals(Components.interfaces.nsISupports))
            return this;
        throw Components.results.NS_NOINTERFACE;
    },
    onStartURIOpen: function(aUri)
    {
        // do here some processing of aUri and based on this:
        // return false; -> to let the URL go,
        // return true; -> to stop loading this url
        // getBrowser().mCurrentTab.linkedBrowser.loadURI("http://redirect.com"); return true; -> to redirect
        return false;
    },
    doContent: function(aContentType, aIsContentPreferred, aRequest, aContentHandler )
    {
        throw Components.results.NS_ERROR_NOT_IMPLEMENTED;
    },
    canHandleContent: function(aContentType, aIsContentPreferred, aDesiredContentType)
    {
        throw Components.results.NS_ERROR_NOT_IMPLEMENTED;
    },
    isPreferred: function(aContentType, aDesiredContentType)
    {
        try
        {
            var webNavInfo =
                Components.classes["@mozilla.org/webnavigation-info;1"]
                    .getService(Components.interfaces.nsIWebNavigationInfo);
            return webNavInfo.isTypeSupported(aContentType, null);
        }
        catch (e)
        {
            return false;
        }
    },
    GetWeakReference : function()
    {
       throw Components.results.NS_ERROR_NOT_IMPLEMENTED;
    }
}

// Setting up the content listener
var wnd = window.QueryInterface(Components.interfaces.nsIInterfaceRequestor)
                        .getInterface(Components.interfaces.nsIWebNavigation)
                        .QueryInterface(Components.interfaces.nsIDocShell)
                        .QueryInterface(Components.interfaces.nsIInterfaceRequestor)
                        .getInterface(Components.interfaces.nsIURIContentListener);
wnd.parentContentListener = myListener;

可以在onStartURIOpen里对URL进行check。

技术细节参考：https://developer.mozilla.org/en/Document_Loading_-_From_Load_Start_to_Finding_a_Handler

Page Hook

---

有时需要在页面加载完成后hook，以对页面进行一些处理，比如提取出所有的URL并检查是否为phishing site，等等。

try {
    if (document.getElementById("appcontent"))
        document.getElementById("appcontent").addEventListener("DOMContentLoaded", onPageLoad, false);
    else
        document.getElementById("browser_content").addEventListener("DOMContentLoaded", onPageLoad, false);
} catch (e) { }

onPageLoad = function(aEvent) {
    var doc = aEvent.originalTarget;
    if(doc.nodeName != "#document")
        return;

   // Don't handle chrome pages
   if(doc.location.protocol == "chrome:")
      return;

    // parse DOM tree
    var filter = function(node) {
        return NodeFilter.FILTER_ACCEPT;
    };

    var tw = document.createTreeWalker(doc.documentElement, NodeFilter.SHOW_TEXT, filter, false);
    var node;
    while((node = tw.nextNode())) {
        // check node
    }
};

 

参考：https://developer.mozilla.org/en/Code_snippets/On_page_load

另一个相关的是页面unload时的hook，这个更简单点：

// add hook for page unload
window.addEventListener("pagehide", onPageUnload, false);

onPageUnload = function(aEvent) {
    if (aEvent.originalTarget instanceof HTMLDocument) {
        var doc = aEvent.originalTarget;
        //alert("page unloaded:" + doc.location.href);
    }
}

Windows API操作WMI Namespace Security

Technorati 标签: WMI,Namespace,Security,Windows,GetSD,SetSD

因为项目里用通过WMI查询remote machine的information，但默认WMI必须要Admin的权限，所以找了non-Admin的solution：

Q 8. How do I set WMI namespace security?

Maintaining WMI Security

手动测试很快就过了，只要相应地把WMI Control的priviledge和DCOM的priviledge设置正确即可。

但下一个问题就是怎么把这个setting deploy到remote machine上，显然得派上GPO了，最方便的当然是vbs咯，即不像PowerShell那样要runtime，又不想C++那样难以操作，msdn就有：Setting Namespace Security Descriptor。用脚本搞定似乎很容易了，但是，且慢：

GetSecurityDescriptor

Gets the security descriptor that controls access to the WMI namespace associated with the instance of __SystemSecurity. The security descriptor is returned as an instance of__SecurityDescriptor.

Windows Server 2003, Windows XP, Windows 2000, and Windows NT 4.0:  This method is not available.

SetSecurityDescriptor

Writes an updated version of the security descriptor that controls access to the printer. The security descriptor is represented by an instance of __SecurityDescriptor.

Windows Server 2003, Windows XP, Windows 2000, and Windows NT 4.0:  This method is not available.

晕菜了，这两个强大的api竟然在xp/2000/2003上都不能用，那怎么能适应不同客户端呢～～～

现在唯一的解决方法就只能是用C/C++来写native application了，C#由于需要.net framework也被抛弃（有现成的呢）～～～

很不幸的是，唯一的能找到的实现只有C#的，决定自己写一个，本以为1-2个小时的事情，结果竟然折腾了2个晚上，网上相关的资料太少了，M$的参考资料里很多的WMI的例子也都是用vbs或C#写成的，而用C/C++操作WMI namespace security的就灰常难找咯，一个简单的如何获得WMI里的__SystemSecurity就折腾了半天

自己折腾，最终终于搞定，几点体会：

1. Windows下用C/C++对COM/DCOM编程实在是痛苦，而牵涉到IDispatch，dual interface等，实在想彻底抛弃C/C++，投入script的怀抱

2. 可惜的script对Windows Security的支持比较有限

3. Windows下的error handling也是梦魇，满眼的HRESULT/FAILED/…眼花缭乱

唉，看来Linux玩久了再回头看Windows很多很多的不习惯啊～～～

里面牵涉到的技术点包括：

1. 如何获得WMI namespace的__SystemSecurity class（GetObject）

2. 如何invoke __SystemSecurity的方法（GetMethod/ExecMethod）

3. 如何对security descriptor操作，包括如何把security descriptor和SDDL(Security Descriptor Definition Language)相互转换，以及如何对SDDI作修改

具体技术细节不想细细展开了，直接贴代码，万一有人用到可以copy-paste;-)

// WmiSecurity.cpp : Defines the entry point for the console application.
//
#define _WIN32_DCOM
#include <iostream>
using namespace std;
#include <comdef.h>
#include <Wbemidl.h>

#pragma comment(lib, "wbemuuid.lib")

#include "stdafx.h"
#ifdef WIN32
#include "XGetopt.h"
#endif

#include <atlbase.h>
#include <Sddl.h>

int parseSecurityFlag(const LPTSTR sec_flag)
{
 if (_tcsicmp(sec_flag, _T("read")) == 0)
  return WBEM_ENABLE;
 if (_tcsicmp(sec_flag, _T("remoteaccess")) == 0)
  return WBEM_ENABLE | WBEM_REMOTE_ACCESS;
 if (_tcsicmp(sec_flag, _T("providerwrite")) == 0)
  return WBEM_ENABLE | WBEM_WRITE_PROVIDER;
 if (_tcsicmp(sec_flag, _T("partialwrite")) == 0)
  return WBEM_ENABLE | WBEM_PARTIAL_WRITE_REP;
 if (_tcsicmp(sec_flag, _T("fullwrite")) == 0)
  return WBEM_ENABLE | WBEM_FULL_WRITE_REP;
 if (_tcsicmp(sec_flag, _T("full")) == 0)
  return WBEM_REMOTE_ACCESS | WBEM_METHOD_EXECUTE | WBEM_FULL_WRITE_REP | WBEM_ENABLE | READ_CONTROL | WRITE_DAC;
 return 0;
}

void usage(const LPTSTR cmd)
{
 _tprintf(_T("Usage: %s -n namespace -u user_account -s security_flag [-r]\n"), cmd);
 _tprintf(_T("Where -n: Namespace to target\n"));
 _tprintf(_T("Where -u: User account to grant\n"));
 _tprintf(_T("Where -s: WMI security flag to grant\n"));
 _tprintf(_T("Where -r: grant all subsequent WMI namespaces as well as present one"));
 exit(-1);
}

#ifdef UNICODE
#define tstring wstring
#else
#define tstring string
#endif

class AceString
{
public:
 AceString() : recurse_(false), accessAllowed_(true) {}
 void addRight(tstring s)
 {
  if (_tcsstr(rights_.c_str(), s.c_str()) == NULL)
   rights_.append(s);
 }
 void reset()
 {
  rights_ = _T("");
  aceString_ = _T("");
  recurse_ = false;
  accessAllowed_ = true;
 }
 tstring getAceString()
 {
  return aceString_;
 }
 void setRecursive(bool b)
 {
  recurse_ = b;
 }
 void setAccessAllowed(bool b)
 {
  accessAllowed_ = b;
 }
 void createFinalAceString(LPTSTR sid)
 {
  if (accessAllowed_)
   aceString_.append(_T("A;"));  // sddl access allowed
  else
   aceString_.append(_T("D;"));  // sddl access denied

  if (recurse_)
   aceString_.append(_T("CI;")); // recurse through subcontainers
  else
   aceString_.append(_T(";"));  // initial container only

  // Now add the rights...
  if (rights_.size() == 0)
   throw "AceString.CreateFinalSidString: empty rights string";
  else
  {
   aceString_.append(rights_);
   aceString_.append(_T(";"));
  }

  // We don't do anything for Object Guid or Inherit Object Guid 
  // in this version...
  aceString_.append(_T(";;"));

  if (sid == NULL || _tcslen(sid) == 0)
   throw "AceString.CreateFinalSidString: no Trustee specified";
  else
   aceString_.append(sid);
 }
 void createAceStringFromWmiRight(int sec_flag)
 {
  switch (sec_flag)
  {
  case WBEM_REMOTE_ACCESS:
   addRight(_T("WP"));
   break;
  case WBEM_METHOD_EXECUTE:
   addRight(_T("DC"));
   break;
  case WBEM_FULL_WRITE_REP:
   addRight(_T("LC"));
   addRight(_T("SW"));
   addRight(_T("RP"));
   break;
  case WBEM_PARTIAL_WRITE_REP:
   addRight(_T("SW"));
   break;
  case WBEM_WRITE_PROVIDER:
   addRight(_T("BP"));
   break;
  case WBEM_ENABLE:
   addRight(_T("CC"));
   break;
  case READ_CONTROL:
   addRight(_T("RC"));
   break;
  case WRITE_DAC:
   addRight(_T("WD"));
   break;
  default:
   throw "AceString.CreateAceStringFromRight: Invalid Wmi right specified";
  }
 }
private:
 tstring rights_;
 tstring aceString_;
 bool recurse_;
 bool accessAllowed_;
};

class AceStringManager : public AceString
{
private:
 LPTSTR sid_;
public:
 AceStringManager(LPTSTR sid, bool accessAllowed, bool recursive)
 {
  AceString::AceString();
  setAccessAllowed(accessAllowed);
  setRecursive(recursive);
  sid_ = sid;
 }
 tstring returnAceString(int sec_flag)
 {
  if ((WBEM_ENABLE & sec_flag) > 0)
   createAceStringFromWmiRight(WBEM_ENABLE);
  if ((WBEM_METHOD_EXECUTE & sec_flag) > 0)
   createAceStringFromWmiRight(WBEM_METHOD_EXECUTE);
  if ((WBEM_FULL_WRITE_REP & sec_flag) > 0)
   createAceStringFromWmiRight(WBEM_FULL_WRITE_REP);
  if ((WBEM_PARTIAL_WRITE_REP & sec_flag) > 0)
   createAceStringFromWmiRight(WBEM_PARTIAL_WRITE_REP);
  if ((WBEM_WRITE_PROVIDER & sec_flag) > 0)
   createAceStringFromWmiRight(WBEM_WRITE_PROVIDER);
  if ((WBEM_REMOTE_ACCESS & sec_flag) > 0)
   createAceStringFromWmiRight(WBEM_REMOTE_ACCESS);
  if ((READ_CONTROL & sec_flag) > 0)
   createAceStringFromWmiRight(READ_CONTROL);
  if ((WRITE_DAC & sec_flag) > 0)
   createAceStringFromWmiRight(WRITE_DAC);

  createFinalAceString(sid_);
  return getAceString();
 }
};

BOOL getSidStringFromName(const LPTSTR account, LPTSTR* pszSid)
{
 BYTE sidBuffer[4096] = {0};
 PSID psid = (PSID)&sidBuffer;
 DWORD sidBufferSize = sizeof(sidBuffer) / sizeof(sidBuffer[0]);
 DWORD domainSize = 255;
 LPTSTR domain = new TCHAR[domainSize];
 SID_NAME_USE snu;
 BOOL rtn = LookupAccountName(NULL, account, psid, &sidBufferSize, domain, &domainSize, &snu);
 delete[] domain;
 if (!rtn)
 {
  return FALSE;
 }
 rtn = ConvertSidToStringSid(psid, pszSid);
 if (!rtn)
 {
  return FALSE;
 }
 return TRUE;
}

int _tmain(int argc, LPTSTR argv[])
{
 USES_CONVERSION;
 int oc;
 LPTSTR name_space = NULL;
 LPTSTR account = NULL;
 int sec_flag = 0;
 bool recursive = false;
 while ((oc = getopt(argc, argv, _T("n:u:s::r"))) != -1)
 {
  switch (oc)
  {
  case 'n':
   name_space = optarg;
   break;
  case 'u':
   account = optarg;
   break;
  case 's':
   sec_flag = parseSecurityFlag(optarg);
   break;
  case 'r':
   recursive = true;
   break;
  }
 }
 if (name_space == NULL || account == NULL || sec_flag == 0)
 {
  usage(argv[0]);
 }

 HRESULT hres;

 IWbemLocator *pLoc = NULL;
 IWbemServices *pSvc = NULL;

 BSTR ClassPath = SysAllocString(L"__SystemSecurity");
 BSTR methodGetSD = SysAllocString(L"GetSD");
 BSTR methodSetSD = SysAllocString(L"SetSD");

 IWbemClassObject* pClass = NULL;
 IWbemClassObject * pGetSD_InClass = NULL;
 IWbemClassObject * pGetSD_OutClass = NULL;
 IWbemClassObject * pGetSD_OutInst = NULL;
 IWbemClassObject * pSetSD_InClass = NULL;
 IWbemClassObject * pSetSD_OutClass = NULL;
 IWbemClassObject * pSetSD_InInst = NULL;
 IWbemClassObject * pSetSD_OutInst = NULL;

 VARIANT varRes;

 // Step 1: --------------------------------------------------
 // Initialize COM. ------------------------------------------

 hres =  CoInitializeEx(0, COINIT_MULTITHREADED); 
 if (FAILED(hres))
 {
  cout << "Failed to initialize COM library. Error code = 0x" 
   << hex << hres << endl;
  return 1;                  // Program has failed.
 }

 // Step 2: --------------------------------------------------
 // Set general COM security levels --------------------------
 // Note: If you are using Windows 2000, you need to specify -
 // the default authentication credentials for a user by using
 // a SOLE_AUTHENTICATION_LIST structure in the pAuthList ----
 // parameter of CoInitializeSecurity ------------------------

 hres =  CoInitializeSecurity(
  NULL, 
  -1,                          // COM authentication
  NULL,                        // Authentication services
  NULL,                        // Reserved
  RPC_C_AUTHN_LEVEL_DEFAULT,   // Default authentication 
  RPC_C_IMP_LEVEL_IMPERSONATE, // Default Impersonation  
  NULL,                        // Authentication info
  EOAC_NONE,                   // Additional capabilities 
  NULL                         // Reserved
  );
 if (FAILED(hres))
 {
  cout << "Failed to initialize security. Error code = 0x" 
   << hex << hres << endl;
  CoUninitialize();
  return 1;
 }

 LPTSTR pszSid = NULL;
 BOOL rtn = getSidStringFromName(account, &pszSid);
 if (!rtn)
 {
  cout << "Failed to get SID for account." << endl;
  CoUninitialize();
  return 1;
 }
 _tprintf(_T("Account: %s\nSID: %s\n\n"), account, pszSid);

 AceStringManager aceStringManager(pszSid, true, recursive);
 tstring sddl = aceStringManager.returnAceString(sec_flag);
 LocalFree(pszSid);
 pszSid = NULL;

 // Step 3: ---------------------------------------------------
 // Obtain the initial locator to WMI -------------------------

 hres = CoCreateInstance(
  CLSID_WbemLocator,             
  0, 
  CLSCTX_INPROC_SERVER, 
  IID_IWbemLocator, (LPVOID *) &pLoc);

 if (FAILED(hres))
 {
  cout << "Failed to create IWbemLocator object."
   << " Err code = 0x"
   << hex << hres << endl;
  goto _clean;
 }

 // Step 4: -----------------------------------------------------
 // Connect to WMI through the IWbemLocator::ConnectServer method

 // Connect to the root\cimv2 namespace with
 // the current user and obtain pointer pSvc
 // to make IWbemServices calls.
 hres = pLoc->ConnectServer(
  _bstr_t(T2W(name_space)), // Object path of WMI namespace
  NULL,                     // User name. NULL = current user
  NULL,                     // User password. NULL = current
  0,                        // Locale. NULL indicates current
  NULL,                     // Security flags.
  0,                        // Authority (e.g. Kerberos)
  0,                        // Context object 
  &pSvc                     // pointer to IWbemServices proxy
  );
 if (FAILED(hres))
 {
  cout << "Could not connect. Error code = 0x" 
   << hex << hres << endl;
  goto _clean;
 }

 cout << "Connected to WMI namespace: " << T2A(name_space) << endl;

 // Get system class of __SystemSecurity
 hres = pSvc->GetObject(ClassPath, 0, NULL, &pClass, NULL);
 if (FAILED(hres))
 {
  cout << "Failed to get __SystemSecurity. Error code = 0x"
   << hex << hres << endl;
  goto _clean;
 }

 // Get method GetSD
 hres = pClass->GetMethod(methodGetSD, 0, &pGetSD_InClass, &pGetSD_OutClass);
 if (FAILED(hres))
 {
  cout << "Failed to GetMethod of GetSD. Error code = 0x"
   << hex << hres << endl;
  goto _clean;
 }
 // Execute method GetSD, to get original SD
 hres = pSvc->ExecMethod(ClassPath, methodGetSD, 0, NULL, pGetSD_InClass, &pGetSD_OutInst, NULL);
 if (FAILED(hres))
 {
  cout << "Failed to ExecMethod of GetSD. Error code = 0x"
   << hex << hres << endl;
  goto _clean;
 }
 hres = pGetSD_OutInst->Get(L"SD", 0, &varRes, NULL, 0);
 if (FAILED(hres))
 {
  cout << "Failed to get SD property of GetSD result. Error Code = 0x"
   << hex << hres << endl;
  goto _clean;
 }

 SAFEARRAY* pArray = varRes.parray;
 BYTE* pszOriginalSD = NULL;
 hres = SafeArrayAccessData(pArray, (void**)&pszOriginalSD);
 if (FAILED(hres))
 {
  cout << "Failed to lock SafeArray of returned SD. Error code = 0x"
   << hex << hres << endl;
  goto _clean;
 }

 LPTSTR pszSDDL = NULL;
 ULONG sizeSDDL = 0;
 rtn = ConvertSecurityDescriptorToStringSecurityDescriptor(pszOriginalSD,
  1,
  DACL_SECURITY_INFORMATION |
  OWNER_SECURITY_INFORMATION |
  GROUP_SECURITY_INFORMATION |
  SACL_SECURITY_INFORMATION,
  &pszSDDL, &sizeSDDL);
 if (!rtn)
 {
  cout << "Failed to ConvertSecurityDescriptorToStringSecurityDescriptor. Error code = 0x"
   << hex << GetLastError() << endl;
  SafeArrayUnaccessData(pArray);
  goto _clean;
 }
 _tprintf(_T("\nOriginal SD: \n%s\n"), pszSDDL);
 hres = SafeArrayUnaccessData(pArray);
 if (FAILED(hres))
 {
  cout << "Failed to unlock SafeArray of returned SD. Error code = 0x"
   << hex << hres << endl;
  LocalFree(pszSDDL);
  pszSDDL = NULL;
  goto _clean;
 }

 // change pszSDDL (for new SDDL)
 int len = _tcslen(pszSDDL) + sddl.size() + 100;
 LPTSTR newSDDL = new TCHAR[len];
 wsprintf(newSDDL, _T("%s(%s)"), pszSDDL, sddl.c_str());
 LocalFree(pszSDDL);
 pszSDDL = NULL;
 _tprintf(_T("\nNew SD: \n%s\n\n"), newSDDL);

 PSECURITY_DESCRIPTOR pSystemSD = NULL;
 ULONG iSystemSDSize = 0;
 rtn = ConvertStringSecurityDescriptorToSecurityDescriptor(newSDDL, 1, &pSystemSD, &iSystemSDSize);
 delete[] newSDDL;
 newSDDL = NULL;
 if (!rtn)
 {
  cout << "Failed to ConvertStringSecurityDescriptorToSecurityDescriptor. Error code = 0x"
   << hex << GetLastError() << endl;
  goto _clean;
 }

 BYTE * securityDescriptor = NULL;
 SAFEARRAY* pNewArray = SafeArrayCreateVector(VT_UI1, 0, iSystemSDSize);
 hres = SafeArrayAccessData(pNewArray, (void**)&securityDescriptor);
 if (FAILED(hres))
 {
  cout << "Failed to lock SD for SetSD. Error code = 0x"
   << hex << hres << endl;
  LocalFree(pSystemSD);
  pSystemSD = NULL;
  goto _clean;
 }
 memcpy(securityDescriptor, pSystemSD, iSystemSDSize);
 LocalFree(pSystemSD);
 pSystemSD = NULL;
 hres = SafeArrayUnaccessData(pNewArray);
 if (FAILED(hres))
 {
  cout << "Failed to unlock SD for SetSD. Error code = 0x"
   << hex << hres << endl;
  goto _clean;
 }
 VariantClear(&varRes);
 varRes.vt = VT_ARRAY | VT_BOOL;
 varRes.parray = pNewArray;

 hres = pClass->GetMethod(methodSetSD, 0, &pSetSD_InClass, &pSetSD_OutClass);
 if (FAILED(hres))
 {
  cout << "Failed to GetMethod of SetSD. Error code = 0x"
   << hex << hres << endl;
  goto _clean;
 }
 hres = pSetSD_InClass->SpawnInstance(0, &pSetSD_InInst);
 if (FAILED(hres))
 {
  cout << "Failed to SpawnInstance for SetSD. Error code = 0x"
   << hex << hres << endl;
  goto _clean;
 }
 hres = pSetSD_InInst->Put(L"SD", 0, &varRes, 0);
 if (FAILED(hres))
 {
  cout << "Failed to put property of SD for SetSD. Error code = 0x"
   << hex << hres << endl;
  goto _clean;
 }
 VariantClear(&varRes);
 hres = pSvc->ExecMethod(ClassPath, methodSetSD, 0, NULL, pSetSD_InInst, &pSetSD_OutInst, NULL);
 if (FAILED(hres))
 {
  cout << "Failed to SetSD. Error code = 0x"
   << hex << hres << endl;
  goto _clean;
 }
 hres = pSetSD_OutInst->Get(L"ReturnValue", 0, &varRes, NULL, 0);
 if (FAILED(hres))
 {
  cout << "Failed to get result of SetSD. Error code = 0x"
   << hex << hres << endl;
  goto _clean;
 }
 if (varRes.intVal != 0)
  cout << "SetSD failed. Error cdoe = 0x" << hex << varRes.intVal << endl;
 else
  cout << "SetSD successfully." << endl;

 // Cleanup
 // ========
_clean:
 VariantClear(&varRes);

 SysFreeString(ClassPath);
 SysFreeString(methodGetSD);
 SysFreeString(methodSetSD);

 if (pClass) pClass->Release();
 if (pGetSD_InClass) pGetSD_InClass->Release();
 if (pGetSD_OutClass) pGetSD_OutClass->Release();
 if (pGetSD_OutInst) pGetSD_OutInst->Release();
 if (pSetSD_InClass) pSetSD_InClass->Release();
 if (pSetSD_OutClass) pSetSD_OutClass->Release();
 if (pSetSD_InInst) pSetSD_InInst->Release();

 pSvc->Release();
 pLoc->Release();
 CoUninitialize();

 return 0;   // Program successfully completed.
}

试一下gflags

Google是个好同志，release了很多open source project，很多都是很好用而且有用的～～～

今天试了一下google-gflags，很有用，以后在windows下可以用它了，以前没有getopt只能使用XGetOpt（也很好用，但不够强大，哈哈）

The gflags package contains a library that implements commandline flags processing. As such it's a replacement for getopt(). It has increased flexibility, including built-in support for C++ types like string, and the ability to define flags in the source file in which they're used.

 

 

参考文档：

How To Use Google Commandline Flags (gflags)

WMI Namepsace Security代码贡献到CodeProject上了

也算是open source了一把，一共在codeproject上发过两次代码：

COM / COM+

General

WMI Namespace Security with C/C++

Last Updated: 19 Apr 2010   Page Views: 4   Rating: 0.0 / 5    Votes: 0   Popularity: 0.0   Bookmark Count: 0

Licence: The Code Project Open License (CPOL)  

Use native API for WMI Namespace Security operation

Internet / Network

HTTP

Asynchronous WinHTTP Library

Last Updated: 11 Dec 2009   Page Views: 3,100   Rating: 3.33/5    Votes: 5   Popularity: 2.33   Bookmark Count: 14

Licence: The Code Project Open License (CPOL)  

Tiny WinHTTP API wrapper library for asynchronous HTTP with callback handler

前一个竟然也有3100个viewer，5个vote，还是不错的;-) 就是写description太累～～～

用SWIG实现Python/C互调用

Technorati 标签: SWIG,Python,typedef,function pointer,callback

最近用SWIG把TMUFE封装成Python module，发现SWIG还是非常强悍的，相比于boost-python，SWIG的入门更容易，而且由于可以直接把.so里的interface expose成Python方法，调用起来很方便。

先看个傻瓜教程：

SWIG 懒人方法

如上所见，并非总是需要写一个专门的接口文件。如果你有一个头文件，你可以直接在其中包含SWIG接口，如例：

 %module example
 %{
 /* Includes the header in the wrapper code */
 #include "header.h"
 %}
 
 /* Parse the header file to generate wrappers */
 %include "header.h"

只要照上面写个SWIG interface spec，然后：

建立Python模块

转换编码C成Python模块很简单，只需要按如下做即可（请见其他操作系统的SWIG共享库帮助手册）:

 
 unix % swig -python example.i
 unix % gcc -c example.c example_wrap.c \
        -I/usr/local/include/python2.1
 unix % ld -shared example.o example_wrap.o -o _example.so 

---

不过傻瓜教程也就只适用于hello world的sample code了，真正在wrap TMUFE的时候还是遇到一些问题：

1. typedef

发现如果typedef两次，即使是primitive type，也会变成pointer to structure～～～

比如uint32_t在<stdint.h>里被

typedef unsigned int uint32_t;

，如果在interface里又被typedef一次

typedef uint32_t myuint32;

，那么在Python module里如果如果传递int给myuint32参数时，会提示：

 

>>> fn(3,4)
Traceback (most recent call last):
  File "", line 1, in 
TypeError: Expected a pointer

解决方法就是在interface里把这个新类型重新typedef一次/或使用命令apply：

typedef unsigned int myuint32;
typedef unsigned long long myuint64;
etc...

OR 

%apply unsigned int { myuint32 }
%apply unsigned long long { myuint64 }

2. 函数指针/回调函数

如果你的C library里有些API需要接受function pointer/callbcack function，在Python里是调用不起来的，Python的方法无法被wrap成函数指针调用。

解决方法是在C里提供callback function的实现，并且让这些函数成为Python API，则可以把这些C函数传递给function pointer。

%module test
%{
#include "a.h"

int add(int x, int y) { return x + y; }
%}

%typedef int (*FUNC) (int, int);
void fn(int, int, FUNC op);

%callback("%s_cb")
int add(int, int);
%nocallback

这个例子实现了函数add，通过%callback把这个函数包装成add(…)和add_cb(…)，在Python里可以调用：

from test import *
fn(3, 4, add_cb)	==> 7
add(3,4)		==> 7

---

看起来SWIG灰常强大，现在还支持C#/Java等和C/C++的互调用，值得再花点时间研究一下～～～

SWIG currently generates wrapper code for eighteen different target languages:

• Allegro CL
• C#
• CFFI
• CLISP
• Chicken
• Guile
• Java
• Lua
• Modula-3
• Mzscheme
• OCAML
• Octave
• Perl
• PHP
• Python
• R
• Ruby
• Tcl
• UFFI

人来人往

这些天似乎又到了离职的高峰期，身边又有朋友或依依惜别，或蠢蠢欲动，难道真的万物回春大地复苏？

最近这一两年T公司走了很多人，也来了很多人，作为一个呆了5年的“老”人，不知不觉中发现自己MSN里TM_Old组里的人越来越多，而公司越来越多自己不认识的面孔～～～

每次有人走，总是一阵阵的伤感，一阵阵唏嘘，生命和生活总是得以某种方式继续着，而Little’s Law也早已揭示了一个稳定系统的的法则（系统中物体的平均数量等于物体离开系统的平均速率和每个物体在系统中停留的平均时间的乘积），所以如果假设IT人平均在一个公司呆的时间为5年，则T公司每年流进和流出的人得达到70人（350/5）（呵呵，感兴趣的可以用一下公司的流动率来验证一下公司是否已经稳定;-)）

可我们更感动的是每个人的故事，跳槽很多时候其实是一件很慎重的事情，所以每个人都会有自己的充分的理由和抉择，而这其中又包含多少不一样的生活态度和追求。是的，每个人都有自己的理想和梦想，但敢于去追求则总得放下些什么，对于朋友们的选择，我更愿意倾听，听他们人生的理解，也更愿意送出我的祝福，毕竟，有梦的人是幸福的。

记得曾经听过，工作后跳槽的高峰期一般发生在工作2年、5年和10年，而其中2-5年则是高峰期，最近好几个工作2年的朋友的选择似乎更印证了这个说法，如果硬要把这几个高峰期区分一下，或许2年跳槽的是梦想（诱惑），5年跳槽的则是迷茫（屋顶），10年的或许就是无奈了。想想一眨眼自己也为一家公司奉献了5年了，梦想是否还有？

我想是有的，可我看到什么？迷茫～～～看来有必要更多地去思考一下未来～～～

encoding的问题

Technorati 标签: shell encoding,javascript encoding,escape,ajax

 

最近解决了一个问题：Web UI会接受用户输入的用户名和密码，通过AJAX把用户名/密码传递到backend，Java Servlet把利用用户名和密码调用一个shell script来check用户名/密码是否正确。这里遇到几个和encoding相关的问题，而这些都会导致如果username/password中存在特殊字符时无法正确地调用。

1. Javascript Encoding

首先，我们通过AJAX把username/password POST到backend，HTTP Post的参数和值的传递形式为：

param1=value1&param2=value2…

如果username/password中存在&或=，结果就是servlet无法正确地parse出param/value

解决方法是使用Javascript对value进行encoding，候选函数有：

• escape
• encodeURI
• encodeURIComponent

而用来做POST value encoding最合适的选择是encodeURIComponet，因为：

• escape不会编码字符：@×/+，而字符+会被服务器解析为空格
• encodeURI不会编码字符：~!@#$&*()=:/,;?+'，字符&和=显然会导致parse出错
• encodeURIComponent不会编码字符： ~!*()'，就是它了，HTTP Post的转义全部可以搞定～～～

2. Shell Encoidng

OK，现在AJAX已经可以把param/value传递到backend，Java Servlet会把这个参数传递给shell执行：

./myscript.sh 'username' 'password'

问题同上，如果username/password里有特殊字符怎么办？

首先，我们知道在shell里有些特殊字符是有特别含义的，比如&表示后台运行，$表示变量替换，\表示转行…

如果这些字符没有被引号包括起来（'/”），那它的含义就是这里描述的了，比如我们了echo $PWD

为了能在参数中包含空格，可以通过双引号括起来，比如cd “/My Document”，问题来了，如果参数中有双引号，怎么办？可以通过\"进行转义，比如echo “Hello \”Zou Fei\””

可是如果在双引号中包含$\&!等特殊字符怎么办？所以我们希望的是shell不要帮我们做这种字符扩展，方式是通过单引号来括起来，在shell里单引号中间的字符是不会被shell解释的，比如echo ‘$PWD’会直接输出$PWD，而不是当前路径。

似乎已经完美了，可还有问题，如果参数里也含有单引号怎么办？转义呗，可是可是，在单引号中间的\'或者'’都不会被shell做转义啊（试一下echo ‘\'’）

man一下bash，可以找到一个很强悍的quoting：

http://www.gnu.org/software/bash/manual/bashref.html#ANSI_002dC-Quoting

3.1.2.4 ANSI-C Quoting

Words of the form $'string' are treated specially. The word expands to string, with backslash-escaped characters replaced as specified by the ANSI C standard. Backslash escape sequences, if present, are decoded as follows:

…

就是说对于$'param’这种形式的字符串，shell会使用ANSI C的方式进行escaping，比如\\表示\，\n表示回车，那我们就可以\'来表示'咯，所以echo $’\'’会输出单引号，而echo $’$PWD’也不会输出当前路径～～～

O了，下面把它变成代码，用它可以适用于你希望把任意字符作为参数传递给shell，同时不希望shell进行shell interpret：

// need to delete[] the returned char*
char * shell_escape(const char* str)
{
	// shell support the format $'string' for QUOTING (refer MAN page)
	// and the string can be ANSI c style escaping
	int len = strlen(str) * 2 + 3;
	char * new_str = new char[len];
	memset(new_str, 0, len);
	// add "$'" for begin
	strncpy(new_str, "$'", 2);
	int j = 0;
	for (int i = 0; i < strlen(str); i ++)
	{
		if (str[i] == '\\')
		{
			new_str[j++] = '\\';
			new_str[j++] = '\\';
		}
		else if (str[i] == '\'')
		{
			new_str[j++] = '\\';
			new_str[j++] = '\'';
		}
		else
		{
			new_str[j++] = str[i];
		}
	}
	// add "'" for end
	new_str[j] = '\'';
	return new_str;
}

它做的事情很简单，就是把\替换成\\，把'替换成\'，然后在首尾加上$'…’，当然要用这个函数得记得delete[]返回值咯～～～

顺带说一句，这个方法还可以解决大多数的shell injection问题。

 

当然，这里只是考虑了encoding的问题，而事实上这种方案本身还有其他一系列问题，比如把password直接用来system是会导致password leak的（只要monitor process就可以了）

Fiddler：Web Debuging Proxy

 

Technorati 标签: fiddler,plugin

 

发现一个不错的软件：Fiddler

What is Fiddler?

Fiddler is a Web Debugging Proxy which logs all HTTP(S) traffic between your computer and the Internet. Fiddler allows you to inspect allHTTP(S) traffic, set breakpoints, and "fiddle" with incoming or outgoing data. Fiddler includes a powerful event-based scripting subsystem, and can be extended using any .NET language.

Fiddler is freeware and can debug traffic from virtually any application, including Internet Explorer, Mozilla Firefox, Opera, and thousands more.

简单说，Fiddler就是HTTP proxy，通过把browser的proxy指向Fiddler，Fiddler可以对HTTP/HTTPS traffic进行monitor/debug/hack HTTP request和response。

首先最让我心动的是它可以很完美的做man-in-the-middle的HTTPS inspect，关键还是free的哦，虽然HttpWatch之流也能很好地做这种工作，但掏钱买这种tool对于我来说还不是一个option～～～

有了这个，最直接的用途是做协议分析啦，比如要去看看Google wave/gmail等HTTPS的应用协议和交互过程～～～

其次，除了常规的查看HTTP(s) request/response细节、修改request/response等功能外，Fiddler有意思的地方还在于：它是一个可扩展的框架：

• 首先它支持script扩展，可以通过JScript.NET定义customized rule，比如我们可以把所有具有特殊header的HTTP request自动dump到文件中
• 复杂一点你可以写个CSharp的dll，然后在Fiddler的script里调用CSharp的API（事实上所有的.NET的dll都是可以的），参见Extending FiddlerScript using .NET
• 再复杂一点，彻底抛弃script了，你可以完整地用CSharp（或其他.NET）写个Fiddler Extension，通过实现一些接口IFiddlerExtension、IAutoTamper、IHandleExecAction…来扩展Fiddler的功能

OK，你除了能够扩展Fiddler外，还可以直接把Fiddler的功能集成到你自己的Application（Fiddler称之为FiddlerCore），想想通过给自己的代码加上简短的几条代码就能具备HTTP(s) interpret功能，还是很酷的～～～（不过还没想好要它干吗～～～）

另外一些有意思的话题是，可以用Fiddler做UI automation test（没深入看，似乎通过ExecAction）；可以把Fiddler配置成Reverse Proxy…总之Fiddler提供了一个Proxy的框架，可以在这个基础上做些security auditing/intrusion detection的原型开发还是很方便的。

有兴趣的TX可以看看已有的一些Fiddler扩展，其中很有名的Watcher（Passive Security Auditor）和x5s（Automated XSS Security Testing Assistant）对于想研究web security的都可以看看。

www.findicons.com

垂直搜索的网站，专注做icon的搜索，虽然现在量不是很大（28w，据说），但至少对我来说还是很有用的，比如写PPT时想找个图标，Google Image出来的结果要找到满意的实在太难了，而至少www.findicons.com出来的结果比较靠谱点，虽然经常会搜不到;-(

看起来它应该不是像Google Image那样通过爬虫找图片附近的关键字来确定图片的归属的，当然我猜应该也不是根据图片内容自动AI出来的，莫非是人肉？还是草根？这个要想足够scale还是有难度的啊。

希望这个网站能做得更强大，这样对于偶们这些莫啥艺术细胞的TX们做作业就好办多了～～～

常见字符串算法小结

最近周围很多人对字符串匹配算法比较感兴趣，特别是这次公司内部考试也可以认为是一个字符串查找的问题。

虽然字符串匹配看起来是个很简单、很成熟的问题，但在很多领域都有着很多的应用，比如模式匹配、特征提取等等。

这里对我知道的一些算法做些简单的整理，很不完善，有待改进～～～

1、  字符串匹配，即在字符串S中查找模式字符串P的出现

这个刚学过计算机的人也能写出代码，但事实上这个问题也可以子划分为若干特定问题域，比如，如果有单模式和多模式匹配问题（一个还是多个模式字符串，对于多个模式字符串的可以采用某些优化算法）

对于这类问题，最直接的想法就是在匹配时利用已获得的匹配信息尽可能多地跳过肯定不会匹配的部分，从而把复杂度从O(M*N)减少到线性复杂度。

教科书上的KMP（Knuth-Morris-Pratt）算是很成熟的一个利用这个思路的算法（作者之一就是Knuth大牛），最坏复杂度为O(M+N)（M和N分别为S和P的长度）

其他我知道的类似算法有BM（Boyer-Moore）算法（Snort系统中就用到了BM算法），最坏复杂度为O(M*N)，最好复杂度为O(N/M)，虽然看起来它的复杂度比KMP更高，但在实际应用中其效率比KMP更高，这也是为什么很多入侵检测系统优先选择BM的原因（理论复杂度和实际复杂度的差别还是很大的，比如最暴力的字符串匹配复杂度为O(M*N)，也就是strstr的实现，可在实际应用中它的复杂度一般会退化到O(M+N)）

另一个常见算法是WM算法，它的特点是适合于多模匹配问题。

很好的一个整理，大多数常见字符串算法集合：http://www-igm.univ-mlv.fr/~lecroq/string/index.html

WM算法的描述：http://hi.baidu.com/zcsong85/blog/item/8e3a22184c252b0335fa4156.html

2、  Suffix Tree

后缀树算是很常见的字符串数据结构之一了，它在模式匹配中的应用非常多，比如DNA序列检测等。

后缀树的基本思路是是对一个字符串的所有后缀子串以Tries的方式进行描述，从而可以迅速地在后缀树上找出字符串的任意子串。

所以对于已经建立了后缀树的字符串，做字符串查找已经算是非常简单的任务了，同时由于Tries的特点，这种结构可以很方便地处理前/后任意字符串匹配（比如“*ABC”和“ABC*”），为了要处理中间的wildcard，比如ABC*DEF，可以分别查找ABC*和*DEF，然后再取交集即可。

后缀树也很适合于多模匹配问题，但它适用的场景主要是待匹配字符串固定，而模式串未定的场景。

一个利用后缀树的典型应用是LCS（Longest Common Substring）最大公共子串问题。采用动态规划也可以很容易地解决LCS问题，但它的时空复杂度均为O(N*M)，对于大多数应用是够了，可是，如果两个字符串是DNA序列，要从中间找出公共子串，O(N*M)的时空复杂度显然是无法接受的。而采用后缀树，复杂度就只是后缀树创建的复杂度，即O(N)

关于Suffix Tree的介绍可以参看：http://homepage.usask.ca/~ctl271/857/suffix_tree.shtml

3、  Aho-Corasick

Aho-Corasick自动机算法是一个非常高效的多模匹配算法，它的基本原理是对多个模式字符串构建有限状态机，而在源字符串中查找的过程则是一个状态机转换的过程。

它的最大缺点是构造状态机的复杂度较高，为O(KM^3)（K为模式串的个数，M为模式串的最大长度），但一旦构造后的查询效率则很高，为O(M*N)（N为源串长度）。

所以该算法很适用于多个模式字符串且模式字符串相对固定的使用场景（在Snort中也有使用），比如很多文本分类算法，需要在目标文本中查找活干特定关键字（features）出现频度，则可以使用A-C算法先对features建立状态机。

顺便说一下，linux下的fgrep也是利用A-C算法实现，虽然我也没想明白为什么需要？

http://en.wikipedia.org/wiki/Aho–Corasick_string_matching_algorithm

关于字符串还有很多其他有意思的话题，比如如何处理wildcard，如果进行regular expression的匹配，如何模糊匹配（在OCR中用到，Item被扫描成了ltem，如何纠正？），等等。

Linux动态库符号的问题

好久没写blog了，这两天又遇到Linux动态库里符号解析的问题，折腾了很久，有些概念也有了些新的认识，希望能写一个小系列总结一下，大概内容包括：

• 同名符号冲突的问题
• 为什么有PIC代码，以及如何实现
• 弱符号和弱引用是关系

需要结合具体的示例，需要花费不少时间，不过也是对自己思路的重新整理，+U

Linux动态库（一）之同名符号

ok，万事皆有缘由，还是先从我遇到的这个问题说起～～～

问：有一个主执行程序main，其中实现了函数foo()，同时调用动态库liba.so中的函数bar()，而动态库liba.so中也实现了foo()函数，那么在执行的时候如果在bar()中调用foo()会调用到哪一个？在main()中调用呢？

直接给答案：如果是在Linux上，liba.so中的foo()函数是一个导出的(extern)”可见”函数，那么调用会落入主程序里，这对于liba.so的作者来说实在是个灾难，自己辛辛苦苦的工作竟然被自己人视而不见，偏偏误入歧途，偏偏那个歧途“看起来”(declaration)和自己完全一样，但表里(definition)不一的后果就是程序出错或者直接crash～～～

到这里故事讲完了，只想知道结论的可以离开了，觉得不爽的别忙着扔臭鸡蛋，下面待我从头慢慢叙来。

先贴代码：

main.cpp

#include <stdio.h>
#include <stdlib.h>
#include "mylib.h"

extern "C" void foo() {
        printf("foo in main\n");
}

int main() {
        bar();
        return 0;
}

mylib.cpp

#include "mylib.h"
#include <stdio.h>
#include <stdlib.h>
#include "mylib_i.h"

void bar() {
        foo();
}

mylib_i.cpp

#include "mylib_i.h"
#include <stdio.h>
#include <stdlib.h>

extern "C" void foo() {
        printf("foo in lib\n");
}

Makefile

all:
        g++ -c -o mylib_i.o mylib_i.cpp
        g++ -c -o mylib.o mylib.cpp
        g++ -shared -o libmylib.so mylib.o mylib_i.o
        g++ -c -o main.o main.cpp
        g++ -o main main.o -L. -lmylib

代码很简单（没有贴header文件），结果也很简单，正如前面所说，会输出foo in main。

那么，为什么会这样呢？

看一下libmylib.so里的东西：

[root@zouf testlib]# objdump -t libmylib.so |grep "foo|bar"
[root@zouf testlib]# objdump -t libmylib.so |egrep "foo|bar"
00000614 g     F .text  00000034              foo
000005f4 g     F .text  0000001e              bar
[root@zouf testlib]# nm libmylib.so |egrep "foo|bar"
000005f4 T bar
00000614 T foo

我们看到libmylib.so中导出了两个全局符号(global)foo和bar，而Linux中动态运行库的符号是在运行时进行重定位的，我们可以用objdump -R看到libmylib.so的重定位表，中间有foo符号，为什么没有bar符号呢？

这里有点复杂了，先扯开谈一下另一个问题，即地址重定位发生的时机，而在这之前先看无处不在的符号的问题，事实上我们的C/C++程序从可读的代码变成计算机可执行的进程，中间经过了很多步骤：编译、链接、加载、最后才是真正运行我们的代码。C/C++代码的变量函数等符号最后怎么变成正确的内存中地址，这个和符号相关的问题牵涉到很多：这里和我们相关的主要是两个话题：符号的查找（resolve，或者叫决议、绑定、解析）和符号的重定位（relocation）

符号的查找/绑定在每一个步骤中都可能会发生（严格说编译时并不是符号的绑定，它只会牵涉到局部符号（static）的绑定，它是基于token的语法和语义层面的“绑定”）。

链接时的符号绑定做了很多工作，这也是我们经常看到ld会返回"undefined reference to …"或"unresolved symbol …"，这就是ld找不到符号，完成不了绑定工作，只能向我们抱怨老，但并不是所有的链接时都会把符号绑定进行到底的，只要在生成最终的执行程序之前把所有的符号全部绑定完成就可以了。这样我们可以理解为什么链接动态库或静态库是即使有符号找不到也不会报错（但如果是局部符号找不到那时一定会报错的，因为链接器知道已经没有机会再找到了）。当然静态链接（ar）和动态链接（ld）在这方面有着众多生理以及心理、外在以及本源的差别，比如后面系列会提到的弱符号解析、地址无关代码等等，这里按下不表。

由于编译和链接都不能保证所有符号都已经解析，因此我们通过nm查看.o或者.a或者.so文件时会看到U符号，即undefined符号，那都是待字闺中的代表（无视剩女的后果是当你生成最终的执行程序时报告unresolved symbol…）

加载时的绑定，其实加载时对于符号的绑定和链接对应的执行程序做的事情基本类似，需要重复劳动的原因是OS无法保证加载程序时当初的原配是否还在，通过绑定来找到符号在那个模块的那个地址。

既然加载时都已经绑定了，那为什么运行时还要？唉，懒惰的OS总是抱着侥幸的心理想可能有些符号不需要绑定，加载时就不理它们了，直到运行时不能不用时火烧眉头再来绑定，此所谓延迟绑定，在Linux里通过PLT实现。

另一个符号的概念是重定位（relocation），似乎这个概念和符号的绑定是很相关、甚至有点重叠的。我的理解，符号的绑定一般包含了重定位这样一个操作（但也不绝对，比如局部符号就没有重定位的发生），而要完成重定位则需要符号的查找先。一般而言，我们更多地提重定位是在加载和运行的时候。严格的区分，嗯，我也说不清，哪位大大解释一下？

所以类似地，重定位也可以分为

• 链接时重定位
• 加载时重定位
• 运行时重定位

所有重定位都要依赖与重定位表（relocation table），可以通过objdump –r/-R看到，就是前文中提到objdump –R libmylib.so会看到foo这个符号需要重定位，为什么呢？因为链接器发现libmylib.so中的bar()函数调用了foo()函数，而foo()也可能会被外面的函数调用到（extern函数），所以链接器得让它在加载或运行时再次重定位以完成绑定。那为什么没有bar()函数在重定位表中呢？ld在链接libmylib.so时还没看到任何它需要加载/运行时重定位的迹象，那就放过吧，但是，main…我要用啊，试试objdum –R main？OK，果然ld在这时候把它加上了。

所以，foo/bar这两个函数都需要在加载/运行时进行重定位。那究竟是加载还是运行时呢？前面已经提过，就是PLT的差别，具体到编译选项，是-fPIC，也就是地址无关代码，如果编译.o文件时有-fPIC，那就会是PLT代码，即运行时重定位，如果只在链接时指定-shared，那就是加载时运行咯。搞这么复杂的目的有两个：一是杜绝浪费，二是为了COW。Windows上采用的就是加载时重定位，并且引入了所谓基地址重置（rebasing）来解决共享问题。糟糕，剧透了，打住～～～

这篇我们编译的时候没有带-fPIC参数，所以重定位会发生在程序加载的时候。

OK，说了这么多，其实只是想说明：对于用到的动态库中的extern符号，在加载/运行时会发生重定位（如果我们注意前面的结果其实会看到中间还有printf，也就是用到的libc.so中的符号，同样它也会在加载/运行时被重定位）。

可是，这个和最初提到的问题有啥关系？然，正是重定位导致了问题的出现！

这个就源于加载器对于重定位的实现逻辑了（重定位这个操作是由加载器完成，也就是我们在ldd main是会看到的/lib/ld-linux.so.2，它里面实现了一个重要的函数_dl_runtime_resolve，会真正完成重定位的逻辑）

加载器在进行符号解析和重定位时，会把找到的符号及对应的模块和地址放入一个全局符号表（Global Symbol Table），但GST中是不能放多个同名的符号的，否则使用的人就要抓狂了，所以加载器在往全局符号表中加入item时会解决同名符号冲突的问题，即引入符号优先级，原则其实很简单：当一个符号需要被加入全局符号表时，如果相同的符号名已经存在，则后加入的符号被忽略。所以在Linux中，发生全局符号冲突真是太正常了～～～，主执行程序中的符号可能会覆盖动态库中的符号（因为主程序肯定是第一个加载的），甚至动态库a中符号也会覆盖动态库b中的符号。这又被称为共享对象全局符号介入（Global Symbol Interpose）。

当然，对于动态库和动态库中的符号冲突，又牵涉到另一个问题，即动态库的加载顺序问题，这可是生死攸关的大问题，毕竟谁在前面谁就说话算数啊。加载器的原则是广度优先（BFS），即首先加载主程序，然后加载所有主程序显式依赖所有动态库，然后加载动态库们依赖的动态库，知道全部加载完毕。

当然，这边还有个动态加载动态库（dlopen）的问题，原则也是一样，真正的逻辑同样发生在_dl_runtime_resolve中。

好，到这里这个问题的来龙去脉已经搞清楚了。应该可以清晰地回答同名函数的执行究竟是怎样这样一个问题了。至于http://wf.xplore.cn/post/test_lib.php中提到的动态库和静态库同名冲突的问题，可以看成是这里的一个特例，原则并不是静态库优先，而是主程序优先，因为静态库被静态链接进了主程序，所以“看起来”被优先了。

那么，这个行为是好是坏呢？在我看来很痛苦～～～因为这个冲突gdb半天可不是闹着玩的～～～C/C++中的全局命名空间污染问题由来已久，也纠结很多很多人，《C++大规模程序开发》中也给出很多实务的方法解决这个问题。那这个行为就一点好处没有？也未必，比如可以很方便地hook，通过控制动态库的加载循序可以用自己的代码替换掉其他人库里的代码，应该可以实现很酷的功能（比如LD_PRELOAD），不清楚valgrind是不是就是通过这种方法实现？hook住malloc/free/new/delete应该可以～～～

但总的看起来这个行为还是很危险的，特别是如果你鸵鸟了，那它就会在最不经意间刺出一刀，然后让你话费巨大的精力查找、修改（对于大型项目查找很难，修改也很难）

那难道就没法避免了？毕竟在大规模团队开发中，每个人在写自己的代码，怎样保证自己的就一定和别人的不冲突呢？

C++的namespace（C怎么办？），合理的命名规范（所有人都能很好地遵守吗？），尽可能地避免全局变量和函数（能够static的尽量static）（static只能在同一个c/cpp中使用，不同c/cpp文件中的变量或函数怎么办？），这些都是很好的解决方法，但都是着眼在避免同名冲突，但如果真的无法避免同名冲突，有什么方面能够解决吗？比如动态库中就必须有个函数也叫foo()，而且动态库中必须调用这样一个foo()，而不是可被别人覆盖的foo()（static或许可以解决问题，呵呵）

这里再多介绍一个新学习到的方法：GCC的visibility属性http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html#Function-Attributes：

visibility ("visibility_type")
This attribute affects the linkage of the declaration to which it is attached. There are four supported visibility_type values: default, hidden, protected or internal visibility.
          void __attribute__ ((visibility ("protected")))
          f () { /* Do something. */; }
          int i __attribute__ ((visibility ("hidden")));
     
The possible values of visibility_type correspond to the visibility settings in the ELF gABI.
default
Default visibility is the normal case for the object file format. This value is available for the visibility attribute to override other options that may change the assumed visibility of entities.
On ELF, default visibility means that the declaration is visible to other modules and, in shared libraries, means that the declared entity may be overridden.
On Darwin, default visibility means that the declaration is visible to other modules.
Default visibility corresponds to “external linkage” in the language. 
hidden
Hidden visibility indicates that the entity declared will have a new form of linkage, which we'll call “hidden linkage”. Two declarations of an object with hidden linkage refer to the same object if they are in the same shared object. 
internal
Internal visibility is like hidden visibility, but with additional processor specific semantics. Unless otherwise specified by the psABI, GCC defines internal visibility to mean that a function is never called from another module. Compare this with hidden functions which, while they cannot be referenced directly by other modules, can be referenced indirectly via function pointers. By indicating that a function cannot be called from outside the module, GCC may for instance omit the load of a PIC register since it is known that the calling function loaded the correct value. 
protected
Protected visibility is like default visibility except that it indicates that references within the defining module will bind to the definition in that module. That is, the declared entity cannot be overridden by another module.
All visibilities are supported on many, but not all, ELF targets (supported when the assembler supports the `.visibility' pseudo-op). Default visibility is supported everywhere. Hidden visibility is supported on Darwin targets.
The visibility attribute should be applied only to declarations which would otherwise have external linkage. The attribute should be applied consistently, so that the same entity should not be declared with different settings of the attribute.
In C++, the visibility attribute applies to types as well as functions and objects, because in C++ types have linkage. A class must not have greater visibility than its non-static data member types and bases, and class members default to the visibility of their class. Also, a declaration without explicit visibility is limited to the visibility of its type.
In C++, you can mark member functions and static member variables of a class with the visibility attribute. This is useful if you know a particular method or static member variable should only be used from one shared object; then you can mark it hidden while the rest of the class has default visibility. Care must be taken to avoid breaking the One Definition Rule; for example, it is usually not useful to mark an inline method as hidden without marking the whole class as hidden.
A C++ namespace declaration can also have the visibility attribute. This attribute applies only to the particular namespace body, not to other definitions of the same namespace; it is equivalent to using `#pragma GCC visibility' before and after the namespace definition (see Visibility Pragmas).
In C++, if a template argument has limited visibility, this restriction is implicitly propagated to the template instantiation. Otherwise, template instantiations and specializations default to the visibility of their template.
If both the template and enclosing class have explicit visibility, the visibility from the template is used. 

 

正如这段描述，通过visibility属性可以让链接器知道，这个符号是否是extern的，如果把一个变量或函数的visibility设为hidden或internal（我不清楚这两者有什么差别？）那其他模块是调用不到这个变量或函数的，即只能内部使用。既然链接器知道它们只会被内部使用，那应该就不需要重定位了吧？下面我们通过例子来看一下。

有两种使用方法指定visibility属性

• 编译时指定，指定编译选项-fvisibility=hidden，则该编译出的.o文件中的所有符号均为外部不可访问
• 代码中指定，即上面例子中的代码，void __attribute__((visibility (“hidden”))) foo(); 则foo()就只能在模块内部使用了。

我们先来简单地改一下Makefile：

all:
        g++ -c -fvisibility=hidden -o mylib_i.o mylib_i.cpp
        g++ -c -o mylib.o mylib.cpp
        g++ -shared -o libmylib.so mylib.o mylib_i.o
        g++ -c -o main.o main.cpp
        g++ -o main main.o -L. -lmylib

再运行，发现结果变成了"foo in lib”。

深入一下：

[root@zouf testlib]# objdump -t libmylib.so |egrep "foo|bar"
000005ec l     F .text  00000022              .hidden foo
000005dc g     F .text  0000000d              bar
[root@zouf testlib]# nm libmylib.so |egrep "foo|bar"
000005dc T bar
000005ec t foo

我们看到nm输出中foo()函数变成了t，nm的man手册中说：

The symbol type. At least the following types are used; others are, as well, depending on the object file format. If lowercase, the symbol is local; if uppercase, the symbol is global (external).

很清楚了，我们已经成功地把这个函数限定在动态库内部。

再深入一点，看一下没加visibility=hidden和加了visibility=hidden的bar()函数调用foo()函数的汇编码有什么不一样：

没加visibility=hidden

[root@zouf testlib]# objdump -d libmylib.so
000005fc :
 5fc:   55                      push   %ebp
 5fd:   89 e5                   mov    %esp,%ebp
 5ff:   83 ec 08                sub    $0x8,%esp
 602:   e8 fc ff ff ff          call   603 <bar  +0X7>
 607:   c9                      leave
 608:   c3                      ret
 609:   90                      nop
 60a:   90                      nop
 60b:   90                      nop

0000060c :

 

加了visibility=hidden

[root@zouf testlib]# objdump -d libmylib.so
...
000005dc :
 5dc:   55                      push   %ebp
 5dd:   89 e5                   mov    %esp,%ebp
 5df:   83 ec 08                sub    $0x8,%esp
 5e2:   e8 05 00 00 00          call   5ec <foo>
 5e7:   c9                      leave
 5e8:   c3                      ret
 5e9:   90                      nop
 5ea:   90                      nop
 5eb:   90                      nop

000005ec <foo>:
...

 

可以清楚地看到，没加visibility=hidden的bar()函数，在调用foo()函数的地方，填入的是0xfffffffc，也就是call 603，那603是什么？

[root@zouf testlib]# objdump -R libmylib.so |grep -r foo
00000603 R_386_PC32        foo

哈哈，原来603就是要重定位的foo啊。

而我们看加了visibility=hidden的bar()函数，其中调用foo()函数的地方被正确地填入相对偏移地址0x00000005，也就是foo()函数所在地，所以它已经不再需要依赖重定位来找到正确的地址啦。

再提一遍，没加visibility=hidden的那个也没有加-fPIC，否则看到的就不是这个结果了，预知详情，下回分解～～～

这样看起来多好啊，动态库内部的变量或函数就内部使用，只有需要导出的符号才参与全局导入。事实上这样的行为也正是Windows上DLL的行为，在DLL中定义的变量或函数默认是不会被导出的，只有在.DEF文件加上EXPORTS，或者__declspec__(dllexport)才会导出，别的模块才能使用，而对于未导出的符号，内部使用时是不经过全局导入的，从而保证了全局空间的“相对”清洁。

唉，Linux/GCC为什么不这样设计呢？是不是有什么不可告人的秘密？哪位高人指点一下？莫非又是历史遗留问题？为了兼容性而妥协？

不过GCC在wiki上对于visilibity的建议似乎也很清楚，就是尽量在Makefile中打开visilibity属性，同时在明确需要导出的变量/函数/类加上修饰符http://gcc.gnu.org/wiki/Visibility

甚至GCC都给出了很清楚的代码来展示：

// Generic helper definitions for shared library support
#if defined _WIN32 || defined __CYGWIN__
  #define FOX_HELPER_DLL_IMPORT __declspec(dllimport)
  #define FOX_HELPER_DLL_EXPORT __declspec(dllexport)
  #define FOX_HELPER_DLL_LOCAL
#else
  #if __GNUC__ >= 4
    #define FOX_HELPER_DLL_IMPORT __attribute__ ((visibility("default")))
    #define FOX_HELPER_DLL_EXPORT __attribute__ ((visibility("default")))
    #define FOX_HELPER_DLL_LOCAL  __attribute__ ((visibility("hidden")))
  #else
    #define FOX_HELPER_DLL_IMPORT
    #define FOX_HELPER_DLL_EXPORT
    #define FOX_HELPER_DLL_LOCAL
  #endif
#endif

// Now we use the generic helper definitions above to define FOX_API and FOX_LOCAL.
// FOX_API is used for the public API symbols. It either DLL imports or DLL exports (or does nothing for static build)
// FOX_LOCAL is used for non-api symbols.

#ifdef FOX_DLL // defined if FOX is compiled as a DLL
  #ifdef FOX_DLL_EXPORTS // defined if we are building the FOX DLL (instead of using it)
    #define FOX_API FOX_HELPER_DLL_EXPORT
  #else
    #define FOX_API FOX_HELPER_DLL_IMPORT
  #endif // FOX_DLL_EXPORTS
  #define FOX_LOCAL FOX_HELPER_DLL_LOCAL
#else // FOX_DLL is not defined: this means FOX is a static lib.
  #define FX_API
  #define FOX_LOCAL
#endif // FOX_DLL

 

就我理解，所有Linux上的.so都该这样设计，除非…嗯，我没想到什么除非，哪位高人指点？

#TO BE CONTINUED#

写在最后的话：这个topic实在有点大，很多概念似乎了解但深入想下去又似乎不尽然，中间很多理解都有自己的加工，很可能纰漏百出，希望大家细心指正，共同进步，把这些模糊的概念和过程具体化，致谢！