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实在有点大,很多概念似乎了解但深入想下去又似乎不尽然,中间很多理解都有自己的加工,很可能纰漏百出,希望大家细心指正,共同进步,把这些模糊的概念和过程具体化,致谢!

相关阅读:

本文网址:http://zoufeiblog.appspot.com/2010/09/24/LinuxSymbolConflict.html

Posted in Uncategorized

Linux动态库符号的问题

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

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

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

相关阅读:

本文网址:http://zoufeiblog.appspot.com/2010/09/20/LinuxLibrarySymbol.html

Posted in Uncategorized

常见字符串算法小结

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

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

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


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,如何纠正?),等等。

本文网址:http://zoufeiblog.appspot.com/2010/07/1/StrMatch.html

Posted in Uncategorized

www.findicons.com

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

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

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

本文网址:http://zoufeiblog.appspot.com/2010/05/5/FindIcons.html

Posted in Uncategorized

Fiddler:Web Debuging Proxy

 

Technorati 标签: ,

 

发现一个不错的软件: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的都可以看看。

本文网址:http://zoufeiblog.appspot.com/2010/05/5/Fiddler.html

encoding的问题

 

最近解决了一个问题: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就可以了)

本文网址:http://zoufeiblog.appspot.com/2010/05/5/Encoding.html