张五常 思想要从一片空白起笔

2006-03-09 17:16:49

老师艾智仁给我最大的影响，是他永远像一个天真小孩那样看问题。当年同学们都听说他是理论高人，智商不凡，但五十岁了，对任何问题彷佛一个小孩子第一次看世界，给我有难以形容的感染力。教功用，他问：什么是功用？教货币，他问：什么是货币？问他一篇大名鼎鼎的关于产出函数的文章，他问：你相信文章里说的吗？这种教育方法之前之后我没有见过。

那时艾师在行内有名，但不像十多年后那样举世知名。我推迟博士课程一年，只为了等艾师从他造访的史坦福回到加大，先听他的课，才考他出的博士理论试题。于今回顾，那是我在经济学习过程中作出的最好一项决定。这决定不是受到同学的影响，而是两个其它原因。其一是一九六二年，麻省理工的森穆逊到我就读的加大演讲。没有谁不知道森氏是当时最负盛名的经济理论家。演讲后一位同学举手提问，森氏说：「让我教你一点价格理论吧。」跟着停下来，游目四顾，说：「对不起，在你们这里我不敢教价格理论！」举座哗然。大家都知道，他的意思是我们有一个艾智仁，而当时艾师不在座。第二个原因，是我拜读过艾师于一九五○年发表的《风险、进化与经济理论》，精妙绝伦，深不可测，于是五体投地，非拜他为师不可。

后来成为艾师的入室弟子。每次入室求教，他总像小孩子般看我提出的问题，次次如是，影响了我对学问的处理方法。说像小孩子般看问题，其实是说从一片空白开始想；之前想过的，再想，也是从一片空白起笔，丝毫传统的成见也没有，自己此前的观点一概不管。朋友，你可以做到吗？如果可以，那么你不是天才也算是准天才了。天才其实就是那样简单的一回事。如果有成见的约束，摆脱不了前人之见，算你智商顶级，思想不可能传世。如果你的智商只是一般，受到成见的约束就会升级为蠢才了。

不要误会，我不是说传统之见什么用处也没有。正相反，我是个尊重传统的人，以经济学为例，我对传统的理论学得通透。然而，尊重传统，熟习传统，接受传统的影响，不等于受到成见的约束或左右。所有的人说这样想才对，你怎样想呢？如果所有的人这样想你就一定要跟着这样想，你就是蠢才。如果所有的人都这样想，你对自己说：知道，但要重新考虑，不认为所有人说对就是对，说错就是错，衡量一下再算，可用的采用，认为不对就不管。这是毫无成见约束的思考，说是天才庶几近矣。

毫无成见约束的思考方法，简言之，是从一片空白起笔，认为传统可用的放进去，不可用的撇开来，然后加进一些自己的。推理逻辑不能错，小心一点就成，推到哪里就哪里。既然自己毫无成见，推出可以传世的新观点的机会是不低的。

我是从艾师那里学会了从一片空白起笔的思考方法的。当年写论文《佃农理论》，在艾师与赫舒拉发的指导下，很有点不敢乱来。我想，边际产出定律是传统的，他们教过，自己怎样想也认为不可能错，要用。竞争的理念我从艾师学得的出自传统，但比传统的远为高明，也要用。成本的概念也是传统的，但不够一般化，改进一点，要用。这样，脑子一片空白，把这三项放进去，搓、搓、搓，砌、砌、砌，推出了自己的佃农理论。结论与传统的相反，是传统错了，而此错也，起于一个佃农「无效率」的成见。

博士论文是三十九年前的事。之后的文章行内朋友认为有新意，主要是因为历来的习惯，每逢考虑一个题材，事前很少研读他家之作，自己想自己的，分析有了结果才参考他人的。四十岁后懒得参考，把文稿写好后才找些有关的论着下注脚，点缀一下。文成后才查考，有时发觉己见与他家相近；很多时不同，但没有冲突；有时特别，己见与他家相反。谁对谁错不是那么重要，重要是找到了真理，而从一片空白想起，彷佛自己在大海飘浮，不知会飘到哪里去，对我来说，是做学问的乐趣所在。

有一个相当固定的规律。同一题材，凡是认为他家之见是错了的，细看之下，他们的见解通常是受了成见的约束。好比价格管制的分析，成见要不是说有短缺，就是说有剩余，不均衡，市场会有什么压力云云。三十三年前我考虑价格管制，这传统分析我当然耳熟能详，但轮到自己用脑，只一个晚上就认为不知所云。短缺、剩余、不均衡等理念皆非事实，看不见，捉不着，只有天晓得是些什么，自己不要这样想下去。于是从一片空白起，想出凡有价格管制必定有价格之外的其它准则定胜负，而这些其它准则会导致租值消散。只要知道哪种准则会被采用，要达到理论的均衡易如反掌。困难是如何推出哪种「其它准则」会被采用。这是个重点，我想了整整一年，直到一个晚上在梦中突然惊觉，传统的租值消散理论全盘错了！有应该消散的租值，不是为了要达到均衡而消散，而是在极大化的假设下，消散的租值是局限下最小的。这就让我们推出在价管之下什么其它准则会被采用，跟着的均衡分析是本科生的习作了。

提到这些，因为网上好些同学的言论，骤耳听来很不对头，为什么同学们会那样想呢？中国的青年怎会蠢得那样离奇？细想之下，同学们其实不蠢，也不是成见深不可拔，而是奇怪地他们往往把成见与己见混合起来，以致我这个老人家听得天旋地转。

告诉同学们吧。成见与新意是加不起来的，因为成见的本身是结论。比方说，佃农的传统成见是无效率，你不可以把农民勤奋耕耘加进去而分析得顺理成章。我们要尊重传统，因为与传统毫无关连的思维免不了怪诞不经，不可取。好些传统的观点或结论是好的，考虑之后我们乐意接受。不容许更改的观点是成见，但容许更改而不更改是另一回事。成见不可取，因为一把成见放进脑子里，就不能有一片空白的思想空间，正如一个画家用的画纸早就有人画上一只乌鸦，怎可以创出什么精彩之作来？

一个大有成就的画家需要很懂得传统的绘画技术，需要吸收众多前人画作的感染，也需要有自己的学问、创意与思维。但每次创作，他是要从一张空白的纸或布起笔的。

重视传统，但不受成见的约束；发挥己见，但要有学问与逻辑的支持。二者皆来得不易。我不怀疑中国青年的天赋了得，但智能这回事，大部分是后天学回来。北京天天在谈改革——这些日子他们推出的改革方案多得很。愚见以为，他们要把教育改革放在第一位置。

睡在图书馆的好日子

2004-05-25 09:05:20

一个美国纽约大学的清贫学生，交不起宿舍房租，偷睡图书馆八个月，被发现了，校方

没有处分，反而安排这学生免费住宿舍。这个有趣而又感人的故事，最近成为国际新闻。

是不同的年代了。当年作研究生，我在洛杉矶加州大学的图书馆断断续续地睡了两年多，不是偷睡，是光明正大的，而「睡馆」的同学还有其它两个。说断断续续，因为当时有自己的小公寓，交得起房租，只为了读书方便而选睡图书馆，不回到自己的公寓去。那时成积好，校方免了学费，作助理教员的月薪大约美元三百，找外快，替教授改卷每份一元，替学校运动员补习每小时五元。那是四十多年前，通胀之前的日子了。

那时大学的图书馆每天开二十四小时，每年开三百六十五天。作研究生的可以申请，在图书馆内拿得一个专用小室（称cubicle），在地上对角可以睡觉。小室内有书桌，桌上的墙有书架，小室有门，可上锁，外人不得闯进也。枱灯是自备的，也带了枕头、被铺、清洁用品之类，而重要的是一枝发热针。后者用于把罐头汤在数分钟内煮开，与饼干同吃大有奇趣。不是没有钱吃得较好的，而是懒得跑到外间吃汉堡包。

住在图书馆，可不是因为在地上睡觉有其过瘾之处，而是要读的书太多，借出搬回家，搬来搬去，很麻烦。看官要知道，图书馆内的书分类，先是一门学问分类，继而专题再分类。要研读一个小专题，可以一下子把所有有关的书籍搬进自己在图书馆内的小室，不用借出去的。馆内有小手推车，满载推进自己的小室，读后满载推到走廊，不须放回原来的书架上去。事实上，图书馆的管理禁止我这种大读客把书放回书架，因为可能弄错编排次序。有这样的服侍，图书馆乃天堂也。只有研究生，有教授推荐信的，才有这样的享受权利。

一天阅读十多本书，可以那样快吗？可以的，因为不是逐字逐句地读，而是随意地翻阅。百分之九十九以上的书都很无聊，毫无创意，多一本不多，少一本不少。问题是求学的人不多翻阅就无从作出判断。老师或同学津津乐道的重要读物，有口皆碑的，与自己所学有关当然要细读。但这个层面的作品，与自己攻读有关的，叠起来不到两英尺。其它很多很多的书，不被重视的，可能有一章半章值得细读，或其中可能提到一些事实，不知是真是假，与他书所载不同，对学问上的思考有助。偶尔碰到一本不见经传但自己认为是要读的，惊喜也。沧海遗珠不常有，但有这回事。当年翻阅群书，找新意，有大海捞针之感，但造学问，捞针总要捞一下。

今天才知道的意外收获，是当年睡在图书馆的日子，苦闷之余找了好些与自己读书考试无关的书籍看。什么鸦片战争、太平天国、明治维新、艺术历史、路易十四……都很有消闲价值。目过不忘，这些是我今天写专栏文章的本钱了。虽说不忘，其实忘了不少。历史的年份有时记错（不会大错，小错无伤大雅吧），而细节免不了有点出入。最难记的是人名与地名。不知何解，年轻时的记忆力，虽然朋友认为是奇异功能，永远记不起他人认为是容易记的人名与地名。我这个人对专用名词显然有抗拒感。

要从世界大同的角度做学问

2004-08-19 14:29:12

山木兄寄来他新出版的《闲读偶舍》，第一篇的名目是《嫉洋如仇鲁迅误打陈焕章》。鲁迅胸襟不阔，笔下磨斧痕迹甚重，而又鄙视像林语堂那种在西方介绍中国文化赚饭吃的学者。陈焕章以《孔门经济学原理》为题在美国写博士论文，鲁迅说陈氏「自己也觉得好笑」，其

轻薄态度有点那个，也有点葡萄是酸的味道。

陈焕章是一百年前到哥伦比亚大学攻读经济的。那个时代能到美国名校攻读的中国学子，不是天才也是才子。然而，从陈氏到我写博士论文的六十年间，留美中国学子的可以数得出的经济博士论文，绝大部分论中国，鬼子佬不容易判断真真假假。轮到我写博士论文，时代转变了，中国专家没有市场，而自己的主要兴趣是价格理论。我于是想，论文一定要以有一般性的理论为重心，中国的资料可以用，但千万不要因为文化背景不同而写得老师无从判断。后来写成的《佃农理论》，其理论有一般性，不分国界，虽然引证的资料大部分取自中国的农业与台湾的土地改革。今天这论文受到注意的只是理论那部分，而自己认为比理论更精彩的中国农业资料的分析，数十年来无人问津。这可见在学问上，无论怎样精彩，没有一般性或世界性的，在国际上不容易杀出重围。不单是只为中国而写中国引不起外人的兴趣，只为美国而写美国也有类同的命运。

自然科学，可取的发现都有一般性，没有国籍。社会科学（包括经济学）可以有「国籍」，但如果缺少了一般性，难以成家。历史学的国籍约束看来最大，要在国际上成家，若不能指出不同国家的共同历史规律，就要指出不同文化会导致不同的史实，而又能解释为什么史实不同。

「东是东，西是西，二者永不会合」这句名言老话，虽然不对，但如果是说东与西不容易会合，却没有错。今天的世界，做学问一定要把这二者会合起来——融合起来——才有希望论成就。这样看吧，融合东与西是当今做学问的必需条件，但不足够。有成就的学问，是把二者融合起来，然后表达一些不怪诞的新意。

不一定是近代的人才可以融合东方与西方而达到大成的。生于东而不知西，或生于西而不知东，但产出东、西大同的作品是有的。这些作者是天才了。唐初孙过庭写《书谱》，论书法，其艺术概念与今天的西方艺术观非常一致。十八世纪莫扎特写的西方音乐，今天的中国人喜欢听。这种人不学有术，只凭预感就打通了不同文化的贯通经脉，的确是天之骄子，令人羡慕。当然，艺术讲感情，而人与人之间的感情互通比较容易，但达到的还不多见。历史上，数之不尽的艺术作品，不同文化背景的人是不能共同欣赏的。不能共同欣赏的艺术不是好艺术，依稀地明白这哲理大约有二百年，一天比一天肯定，到今天一般的艺术家都明白，都同意。

在概念与感受上，视觉或听觉艺术是比较容易融合东方与西方的。要通过翻译的诗文就比较困难了。但如果你是今天的中国诗人，懂西语但对西方的诗毫无感受，你不可能是一个有成就的中国诗人。你可以因为天才横溢，不懂西语而成为一个伟大的中国诗人，但你不可以懂西语，毫不欣赏西方的诗，而在写诗上有可观的成就。如果你和我差不多，写诗的天赋不足但要在写诗的造诣上有点成就，那么中语西语皆通，中、西双方的诗皆读，融合起来，当可事半功倍。

不是低估董桥与陶杰这二君子的天赋，但我相当肯定，如果他们不是中西兼通，对西方文学有体会，他们的中语文字不可能达到我们读到的水平。这是融会东方与西方的文化的效果，是从世界大同的角度下笔了。

打通中、西融合的经脉，不容易，需要一段日子，而每个过了关的人会有不同的经历。

我自己的经历，是起头很困难。那是四十七年前，初到多伦多贵境。有两个障碍。其一是老生常谈的东是东，西是西，在脑子里自己划下界线。其二是在西洋鬼子面前不敢示弱，很有点要以炎黄子孙的文化把西洋鬼子的比下去的意识。于今回顾，正如鲁迅写陈焕章，「自己也觉得好笑」。

后来在多伦多遇到一位年纪比我略长的名叫王子春的朋友，其英语文采好得出奇，也有学问，不厌其烦地指导了我几个月，使我茅塞顿开。其后转到美国的洛杉矶，就读于该市的加大，屡遇大师指导，是四十五年前开始的了。

我感到自己完全中西不分，融合得通透，大概是进入加大后的第四年，即是在研究院的第二年，在西方生活了近六个年头了。从本科生起我选科选得杂，这有帮助。进入了研究院我索性住在图书馆乱读一通，不到两年就恍然而悟：原来地球上的学问都是一样，有好有不好，精彩的少胡说的多，而中国的学问，虽有可取，但一般不及西方。其中主要分别，是西方的学问佳作，在有深度的同时说得清楚。是在天天强逼自己想得清楚的日子中，我意识到学问就是学问，没有国界，而中国人做学问的一大缺失，是想得不够清楚。

炎黄子孙的文化传统的学问不是没有深度，而是喜欢吹毛求疵，数树木而不看森林，似乎永远拿不着重点。这种学问很容易故扮高深，把模糊看为深奥，不知为知之，不懂的往往盲目附从，坚持自己看到了皇帝的新衣。如果学问是从世界大同的角度看，没有国籍，做学问就逼着要看森林，而这样看，懂是懂，不懂是不懂，湛深的学问不会真的深不可测，那才算是走进了学问之门。高斯和我曾经说，我们怎样也不明白的经济理论，应该都是错的。

提到这些，起于我关心中国的青年。听到同学们给我提供的今天网页上的好些青年的言论，不以为然，认为他们在追求知识的重要路途上走错了方向。激情远超理智，不分客观与主观之别，不知道推理必须有假设，而又往往自以为是，不懂就以专家自居。只读过几本书，一知半解，就以为有了学问，以为知道真理。这是数树木的途径，过不久就会迷失在森林中。

在知识与理智的表达上，香港网页上的青年远胜国内的。求学的际遇不同，所以有别。我关心的是国内的青年。基因说，他们的天赋与香港的没有分别。只是香港的生长于一个国际都市，无论学与问，他们的世界大同的意识抢先了几个马位。还不能说是一般地达到世界大同的学问境界，但比国内的接近得多了。

从今天的世界看，有国籍的学问，皆非上品。

第二篇：张五常2

AnArchitectureforanAdaptiveIntrusion-TolerantServer??

AlfonsoValdes,MagnusAlmgren,StevenCheung,YvesDeswarte????,BrunoDutertre,JoshuaLevy,HassenSa¨?di,VictoriaStavridou,andTom′asE.Uribe

SystemDesignLaboratory,SRIInternational,333RavenswoodAve.,MenloPark,CA94025valdes@

Abstract.Wedescribeageneralarchitectureforintrusion-toleranten-terprisesystemsandtheimplementationofanintrusion-tolerantWebserverasaspeci?cinstance.Thearchitecturecomprisesfunctionallyre-dundantCOTSserversrunningondiverseoperatingsystemsandplat-forms,hardenedintrusion-toleranceproxiesthatmediateclientrequestsandverifythebehaviorofserversandotherproxies,andmonitoringandalertmanagementcomponentsbasedontheEMERALDintrusion-detectionframework.Integrityandavailabilityaremaintainedbydy-namicallyadaptingthesystemcon?gurationinresponsetointrusionsorotherfaults.Thedynamiccon?gurationspeci?estheserversassignedtoeachclientrequest,theagreementprotocolusedtovalidateserverreplies,andtheresourcesspentonmonitoringanddetection.Alertstrig-gerincreasinglystrictregimestoensurecontinuedservice,withgracefuldegradationofperformance,evenifsomeserversorproxiesarecompro-misedorfaulty.Thesystemreturnstolessstringentregimesasthreatsdiminish.Serversandproxiescanbeisolated,repaired,andreinsertedwithoutinterruptingservice.

1Introduction

Thedeploymentofintrusion-detectiontechnologyonmission-criticalandcom-mercialsystemsshowsthatperfectdetectionandimmediatemitigationofat-tacksremainelusivegoals.Evensystemsdevelopedatgreatcostcontainresidualfaultsandvulnerabilities.Inpractice,emphasismustshiftfromunattainable“bulletproof”systemstoreal-worldsystemsthatcantolerateintrusions.Anintrusion-tolerantsystemiscapableofself-diagnosis,repair,andreconstitution,whilecontinuingtoprovideservicetolegitimateclients(withpossibledegra-dation)inthepresenceofintrusions[6].Thispaperdescribestheconceptual??

????ThisresearchissponsoredbyDARPAundercontractnumberN66001-00-C-8058.Theviewshereinarethoseoftheauthorsanddonotnecessarilyre?ecttheviewsofthesupportingagency.ApprovedforPublicRelease—DistributionUnlimited.LAAS-CNRS,Toulouse,France

B.Christiansonetal.(Eds.):SecurityProtocols2002,LNCS2845,pp.158–178,2004.cSpringer-VerlagBerlinHeidelberg2004??

AnArchitectureforanAdaptiveIntrusion-TolerantServer159

COTS Application Servers

ProxiesLeaderIDS

Clients

Fig.1.Schematicviewoftheintrusion-tolerantserverarchitecture

architectureofsuchasystem,andourexperiencewithitsinitialimplementa-tion.Ourdesignintegratesconceptsfromdistributedintrusiondetection,faulttolerance,andformalveri?cation.Ourprimaryconcernsareavailabilityandintegrity:thesystemmustremaincapableofcorrectlyservicingrequestsfromhonestclientsevenifsomecompo-nentsarecompromised.Thearchitectureisalsointendedtobescalable:serversandproxiescanbeaddedtoimprovethesystem’sperformanceandreliability,dependingontheresourcesavailable.

1.1ArchitectureOutline

Thearchitecture,showninFigure1,consistsofaredundanttoleranceproxybankthatmediatesrequeststoaredundantapplicationserverbank,withtheentirecon?gurationmonitoredbyavarietyofmechanismstoensurecontentintegrity,includingintrusion-detectionsystems(IDSs).Theproxiesandapplicationserversareredundantincapabilitybutdiverseinimplementation,sothattheyareunlikelytobesimultaneouslyvulnerabletothesameattack.Theapplicationserversprovidetheapplication-speci?cfunctionalityusingCOTSproducts,thusreducingthecostofspecializedcustom-builtcomponents.Theremainderofthecon?gurationprovidesintrusiontolerancebydetecting,masking,andrecoveringfromattacksornonmaliciousfaults.Thesystemisdesignedtoprovidecontinuedreliableandcorrectservicetoexternalclients,evenifafractionoftheapplicationserversandproxiesarefaulty.Thefaultsweconsiderincludetransientandpermanenthardwarefaults,softwarebugs,andintrusionsintoapplicationserversandtoleranceproxies.Thearchitecturecansupportavarietyofclient-serversystems,suchasdatabaseapplicationsorWebcontentdistribution,undertheassumptionsoutlinedbelow.

160A.Valdesetal.

Animportantaspectofoursystemisadistributedmanagementfunctionthattakesactionsinresponsetoadverseconditionsanddiagnoses.Allplatformsandnetworkinterfaceswithinthesystemareinstrumentedwithavarietyofmoni-torsbasedonsignatureengines,probabilisticinference,andsymptomdetection.Giventhereportsfromthismonitoringsubsystem,themanagementfunctionundertakesavarietyoftolerancepolicyresponses.Responsesincludeenforcingmorestringentagreementprotocolsforapplicationcontentbutreducingsystembandwidth,?lteringoutrequestsfromsuspiciousclients,andrestartingplat-formsorservicesthatappearcorrupt.

1.2Assumptions

Weassumethatattackersdonothavephysicalaccesstothecon?guration.Weassumethatnomorethanacriticalnumberofserversareinanundetectedcompromisedstateatanygiventime.Ouragreementprotocolsassumethatallnonfaultyandnoncompromisedserversgivethesameanswertothesamerequest.Thus,thearchitectureismeanttoprovidecontentthatisstaticfromtheenduser’spointofview.Thereplytoarequestcanbetheresultofsubstantialcomputation,ontheconditionthatthesameresultbeobtainedbythedi?erentapplicationservers.Targetapplicationsincludeplan,catalog,andnewsdistributionsites.Thesystemcontentcanbeupdatedperiodically,bysuspendingandthenresumingtheproxybank,butwedonotaddressspeci?cmechanismsfordoingso(notingonlythatonlinecontentupdatescanintroducenewvulnerabilities).Survivablestoragetechniques[16,23]canbeusedinthefuturetobuildaseparatesubsystemtohandlewriteoperations,whileretainingthecurrentarchitectureforreadrequests.Thearchitecturefocusesonavailabilityandintegrity,anddoesnotaddresscon?dentiality.Wedonotdefendagainstinsiderthreatornetwork-?oodingdenial-of-serviceattacks.

1.3PaperOutline

Section2describesthebasicbuildingblocksofourarchitecture.Section3de-scribesthemonitoringmechanisms,whichaimtoprovideapictureofthecurrentsystemstate,includingsuspectedintrusionsandfaults.Section4describeshowthisinformationisusedtorespondtothreats,adaptingthesystemcon?gurationtotheperceivedsystemstate.Section5describesthedetailsofourimplementa-tion,andSection6presentsourconclusions,includingrelatedandfuturework.2

2.1ArchitectureComponentsApplicationServers

Inourarchitecture,thedomain-speci?cfunctionalityvisibletotheenduser(theclient)isprovidedbyanumberofapplicationservers.Theseprovideequivalent

AnArchitectureforanAdaptiveIntrusion-TolerantServer161

services,butondiverseapplicationsoftware,operatingsystems,andplatforms,sothattheyareunlikelytobevulnerabletocommonattacksandfailuremodes.TheyincludeIDSmonitorsbutareotherwiseordinaryplatformsrunningdiverseCOTSsoftware.Inourinstantiation(seeSection5),theseserversprovideWebcontent.Forourcontentagreementprotocolstobepractical,weassumethereareatleastthreedi?erentapplicationservers;atypicalnumberwouldbe?veorseven.However,theenterprisecanaddasmanyoftheseasdesired,increasingtheoverallperformanceandintrusion-tolerancecapabilities.1

2.2ToleranceProxies

Thecentralcomponentsofourarchitectureareoneormoretoleranceproxies.Proxiesmediateclientrequests,monitorthestateoftheapplicationserversandotherproxies,anddynamicallyadaptthesystemoperationaccordingtothereportsfromthemonitoringsubsystem(describedinSection3).Oneoftheproxiesisdesignatedastheleader.Itisresponsiblefor?ltering,sanitizing,andforwardingclientrequeststooneormoreapplicationservers,implementingacontentagreementprotocolthatdependsonthecurrentregime,whilebalancingtheload.Inthepresenceofperceivedintrusions,increasinglystringentregimesareusedtovalidateserverreplies.Theregimeisselectedac-cordingtoachosenpolicy,dependingonreportsfromthemonitoringsubsystemandontheoutcomeoftheagreementprotocolcurrentlyinuse.Optionalauxiliaryproxiesmonitorallcommunicationbetweentheproxyleaderandtheapplicationservers,andarethemselvesmonitoredbytheotherproxiesandthesensorsubsystem.Ifamajorityofproxiesdetectaleaderfailure,aprotocolisexecutedtoelectanewleader.Ourcurrentdesignandimplemen-tationfocusesonthecaseofasingleproxy.However,wediscussinter-proxyagreementprotocolsfurtherinSection4.4.Thetoleranceproxiesrunonlyarelativelysmallamountofcustomsoftware,sotheyaremuchmoreamenabletosecurityhardeningthanthemorecomplexapplicationservers,whosesecuritypropertiesarealsomoredi?culttoverify.Webelievethereisgreaterreturn,bothintermsofsecurityandutility,inexpendinge?ortdevelopingasecureproxybankthanindevelopinghardenedapplicationservers.Sincetheproxiesaremostlyapplication-independent,theirdevelopmentcostcanbeamortizedbyre-usingthemindi?erentdomains.

2.3Intrusion-DetectionSystem

Thethirdmaincomponentofourarchitectureisanintrusion-detectionsystem(IDS),whichanalyzesnetworktra?candthestateoftheserversandproxiestoreportsuspectedintrusions.SomeIDSmodulesexecuteononeormorededicatedhardwareplatforms,whileothersresideintheproxiesandapplicationservers.WedescribeourIDScapabilitiesinmoredetailinSections3.1and5.1.1Thearchitectureshouldbemodi?edforlargenumbersofapplicationservers,asdiscussedinSection6.

162A.Valdesetal.

2.4FunctionalOverview

Whenaclientrequestarrives,thefollowingstepsareperformed:

1.Theproxyleaderacceptstherequestandchecksit,?lteringoutmalformedrequests.2.Theleaderforwardstherequest,ifvalid,toanumberofapplicationservers,dependingonthecurrentagreementregime.3.Theapplicationserversprocesstherequestandreturntheresultstotheproxyleader.Ifsu?cientagreementisreached,theproxyforwardsthecon-tenttotheclient.4.Theregimeisadjustedaccordingtotheresultofthecontentagreementandreportsfromthemonitoringsubsystem.5.Theauxiliaryproxies,ifpresent,monitorthetransactiontoensurecorrectproxyleaderbehavior.

3MonitoringSubsystem

Themonitoringsubsystemincludesadiversi?edsetofcomplementarymecha-nisms,includingtheIDS.Theinformationcollectedbythemonitoringsubsystemisaggregatedintoaglobalsystemview,usedtoadaptthesystemcon?gurationtorespondtosuspectedordetectedthreatsandmalfunctions,asdescribedinSec-tion4.Diversityhelpsmakethemonitoringsubsystemitselfintrusion-tolerant,sinceitmaystillbee?ectiveifsomeofitscomponentsfail.

3.1IntrusionDetection

Ourintrusion-detectionsystemsfeaturediverseeventsources,inferencetech-niques,anddetectionparadigms.TheyincludeEMERALDhost,network,andprotocolmonitors[19,15,20,29],aswellasembeddedapplicationmonitors[1].Di?erentsensorscoverdi?erentportionsofthedetectionspace,andhavedi?erentdetectionrates,falsealarmratios,andoperationalconditions(e.g.,themaximumrateofincomingeventsthatcanbehandled).Theircombinationallowsdetectingmoreknownattacks,aswellasanomaliesarisingfromunknownones.Theadvantagesofheterogeneoussensorscomeatthecostofanincreasednumberofalerts.Toe?ectivelymanagethem,theymustbeaggregatedandcorrelated[30,18].Alertcorrelationcanalsodetectattacksconsistingofmultiplesteps.

3.2ContentAgreement

Theproxyleadercomparesqueryresultsfromdi?erentapplicationservers,ac-cordingtothecurrentagreementregime,asdescribedinSection4.1.Iftwoormoreresultsfailtomatch,thisisviewedasasuspiciousevent,andsuspectserversarereported.

AnArchitectureforanAdaptiveIntrusion-TolerantServer163

3.3Challenge-ResponseProtocol

Eachproxyperiodicallylaunchesachallenge-responseprotocoltochecktheserversandotherproxies.Thisprotocolservestwomainpurposes:

–Itprovidesaheartbeatthatchecksthelivenessoftheserversandotherprox-ies.Ifaproxydoesnotreceivearesponsewithinsomedelayafteremittingachallenge,itraisesanalarm.–Theprotocolcheckstheintegrityof?lesanddirectorieslocatedonremoteserversandproxies.

Theintegrityofapplicationserversisalsoveri?edindirectlybycontentagree-ment,asmentionedabove.However,aresoluteattackercouldtakecontrolofseveralserversandmodifyonlyrarelyused?les.Thechallenge-responseproto-colcountersthisbyreducing?leerrorlatency,detecting?lemodi?cationsbeforetheyreturnincorrectcontenttotheusers.Asanintegritycheck,thechallenge-responseprotocolissimilartoTripwireTM

[28].Foreachdataitemwhoseintegrityistobechecked,achecksumiscomputedfromasecretvalue(thechallenge)andthecontentoftheitem.Toresistpossibleguessesbyanattacker,thechecksumiscomputedbyapplyingaone-wayhashfunctiontotheconcatenationofthechallengeandthecontenttobechecked.Theresultingchecksumisthencomparedwithaprecomputedone.Thisissu?cienttocheckifstaticdataitemshavebeenmodi?ed.However,wemustalsoconsiderthepossibilitythatanattackerwithcompletecontrolofaserverorproxymodi?estheresponseprogramtoreturnacorrectchallengeresponsefora?leincorrectlymodi?ed.Inparticular,ifthechallengeisalwaysthesame,itiseasyfortheattackertoprecomputeallresponses,storetheresultsinahiddenpartofthememoryordisk,andthenmodifythedata.Theattackerwouldthenbeabletoreturncorrectresponsesforincorrect?les.Toguaranteethefreshnessoftheresponsecomputation,adi?erentchallengeissentwitheachrequest.Theproxycouldcheckthateachresponsecorrespondstothespeci?edchallengebykeepingalocalcopyofallsensitive?lesandrunningthesamecomputationastheserver,butthisimposesanextraadministrativeandcomputationalloadontheproxy.Instead,wecanexploitthefactthatserversandproxiesareperiodicallyrebooted(e.g.,onceaday),asameasureforsoftwarerejuvenation[11].Inthiscase,a?nitenumberCofchallengescanbegeneratedo?ineforeach?letobechecked,andthecorrespondingresponsescomputedo?ine,too.Theresultsarethenstoredontheproxy.Ateachintegrity-checkperiod,theproxysendsoneoftheCchallengesandcomparestheresponsewiththeprecomputedresult.Thechallengesarenotrepeated,provided

C>(timebetweenreboots)×(frequencyofchallenge-responseprotocol).Anattackercouldcircumventthismechanismbykeepingcopiesofboththeoriginalandthemodi?ed?les.Butsuchalarge-footprintattackshouldbede-tected,eitherbycheckingtheintegrityoftheconcerneddirectories,orbythehostmonitorIDS.

164A.Valdesetal.

3.4OnlineVeri?ers

Aspartofthedesignprocess,weexpressthehigh-levelbehavioroftheproxyasareactivesystemthatcanbeformallyveri?ed.Anabstractionofthesystemisdescribedusinga?nite-stateomega-automatonandthepropertiesofinterestarespeci?edintemporallogic.Thehigh-levelspeci?cationscanbeformallyveri?edusingmodelchecking[10].However,thisdoesnotguaranteethattheimplementation(theconcretesystem)meetsthecorrespondingrequirements.To?llthisgap,weintroduceonlineveri?ers,whichcheckthattheabstractpropertiesholdwhiletheconcretesystemisrunning,bymatchingconcreteandabstractstates.Ifanunexpectedstateisreached,analarmisraised.Onlytem-poralsafetypropertiescanbecheckedinthisway[27];however,thechallengeresponseheartbeatdescribedinSection3.3providesacomplementarylivenesscheck.Theonlineveri?ersaregeneratedbyannotatingtheproxyCprogramsource.Sincetype-safenessisnotguaranteed,andonlyhigh-levelpropertiesarechecked,thisdoesnotdetectlower-levelfaults,suchasbu?erover?ows.Wewillapplycomplementarymechanismsatthislevel,suchascompilationusingtheStack-Guardtool[2].

4AdaptiveResponse

Wenowdescribehowthesystemrespondstostatechangesreportedbythemonitoringsubsystemdescribedintheprevioussection.

4.1AgreementRegimesandPolicies

Amainroleplayedbytheproxyleaderistomanagetheredundantapplicationservers.Theproxydecideswhichapplicationserversshouldbeusedtoanswereachquery,andcomparestheresults.Thenumberofserversusedtradeso?systemperformanceagainstcon?denceintheintegrityoftheresults.Figure2presentsthemainstepsinthecontentagreementprotocolexecutedbytheproxyleader.Thisprotocolisparameterizedbyanagreementregime,whichmustspecify,ateachpointintime:

1.Whichapplicationserverstoforwardtherequestto2.Whatconstitutessu?cientagreementamongthereplies3.Whichservers,ifany,toreportassuspicioustothemonitoringsubsystemAgoodagreementregimeshouldperformloadbalancingandchoosetheapplicationserversasrandomlyaspossible,soattackerscannotalwayspredictwhichserverwillserviceaparticularrequest.Mostimportant,theregimeshouldbedynamicallyadjustedinresponsetoalerts:apolicyspeci?estheactiontotakenextifnoagreementisachieved,andwhichregimetouseinresponsetovariousevents.Apolicymustalsospecifyhowtorespondifintrusionsorotheradverseconditionsaredetected,andwhento

AnArchitectureforanAdaptiveIntrusion-TolerantServer

165

Fig.2.Genericcontentagreementprotocol

returntoalessstringentagreementregime.Thetransitiontoastricterregimecanalsooccurasaresultofadministrativeaction(e.g.,iftheadministratorisalertedbyexternalsources).

Example1(Simpleagreementregime).GivenanarchitecturewithNapplicationservers,thesimpleagreementregimen,for1≤n≤N,speci?esthateachclientrequestbeforwardedtondi?erentapplicationservers,randomlychosen,thatarenotconsideredcompromised.Su?cientagreementisreachedifamajorityofservers(atleast??n/2??+1)agree;machinesintheminorityarereportedassuspicious.Theabsenceofareplyiscountedasavoteintheminority.

Werefertosimpleagreementregimes1,2and3assingle,duplexandtriplexmodes,respectively.Theagreementregimewhereeachclientrequestissenttoallapplicationserversisreferredtoasfullmode.Morecomplexregimesarepossible:

Example2(Probabilisticagreementregime).Aprobabilisticagreementregimeassignstoeachserverareal-valuedcon?dence,asanestimatedprobabilityofnoncompromise.Givenarequest,theleaderchoosesasetofserverssuchthatthesumoftheircon?dencesisgreaterthanachosenlowerbound.Resultsarerankedbythesumofthecon?dencesofthemachinesthatproducedthem.Ifthetop-rankedresult’scon?denceexceedsagiventhreshold,itisused.Thecon?denceforserversintheweightedminorityisreduced,andthemonitoringsubsystemisnoti?ed.

166A.Valdesetal.

Table1.Probabilityofsendingcorruptedcontent,queryingonemoreserverincaseofatie010.200020.40.30.300140.8111511111

Onepossiblepolicyusesthesimpleagreementregimesandqueriesonemoreserverifnomajorityisobtained;amoreconservativepolicycouldmovedirectlytofullmodeinstead.Intheprobabilisticcase,moreserverscanbequeriedifthetop-rankedreplydoesnotreachthedesiredcon?dencelevel.Suspiciousapplica-tionserversaretakeno?ineforfurtherdiagnosisandrepair(seebelow).Notethattheagreementprotocolisjustonemechanismofmanytoguardagainstcorruptionofcontent.Tocausethesystemtoprovideinvalidcontent,anattackermustcorruptmultipleserverssimultaneouslysothattheyprovidethesameincorrectcontent,whileevadingtheIDSandchallenge-responseprotocol.Anycontentcorruptiondetectedbythesestrongermechanismsisimmediatelyrepaired.Theagreementprotocolisintendedtomakedeliveryofcorruptcontentveryunlikely,aslongasassumptionsaboutthemaximalnumberofsimultane-ouslycompromisedservershold.

4.2Riskvs.Performance

Thechoiceofpolicyposesatradeo?betweenwhatisconsideredtheacceptableriskofbadcontentdeliveryversusthesystemperformancerequirements.ThereliabilityofanyparticularregimedependsonthequalityoftheIDSalertsandonthefaultassumptionsmade.Givenassumptionsaboutthenumberoffailedservers,wecanestimatetheprobabilitythatthecontentprovidedtoaclientunderagivenpolicyisnotcorrect.Asanillustration,considerthesimpleagreementregimeofExample1.LetNbethenumberofapplicationservers,Fbethetotalnumberofcompro-misedservers,andnbethestartingsimpleregime(numberofqueriedservers).Thefollowingfocusesonintegrity:tocausedeliveryofcorruptcontent,anat-tackermustmodifycontentidenticallyonallcompromisedservers.Thisistheworst-caseassumptionfromtheintegritypointofview.2

Table1showstheprobabilityofsendinganincorrectresponseforN=5,usingapolicythatstartswiththesimpleregimenandqueriesoneextraserverincaseofatie,assumingthatallFcompromisedserversagreeintheirincor-rectresponse.Thehigherregimesreducetheprobabilityofincorrectresponseandincreasetheprobabilityofdetectingcompromisedservers,providedonly2Iftheattackerwishestodenyavailability,contentcorruptioncanbearbitrary;noreplywillbesentiftheprotocolfails.

AnArchitectureforanAdaptiveIntrusion-TolerantServer167

aminorityofserversarefaulty(F≤2).Induplexmode,serviceintegrityisguaranteedifatmostoneserveriscompromised,butsomerequestsmayreceivenoresponse,unlessthepolicyincreasestheregime.Intriplexmode,continuedandcorrectserviceisguaranteedifoneserveriscompromised,butthesystemo?ersareducedcapacitytoclients.Thefullregimeprovidescorrectservice(withperformancedegradation)ifseveral,butnotamajority,oftheserversarecompromised(upto2forN=5).

4.3ResponsestoAlerts

Alertsareindicationsofpossibleattacksorcompromises.ExperienceshowsthatallsystemsconnectedtotheInternetareregularlyattacked,oratleastprobed.IDScomponentsgeneratealargenumberofvalidalertsthatdonotalwaysindicatesystemcompromise,aswellasnumerousfalsealarms.Otherpartsofthemonitoringsubsystemgeneratealertsaswell:thecontentagreementandchallenge-responseprotocolsprovidealertsthatidentifylikelycompromises.Althoughalertscanarisefromdirectdetectionofanattack,manyreportsymptomsofacompromisethathasalreadyoccurred.Whileattackdetectionusuallyindicatesonlythepossibilityofacompromise,symptomdetectioncanreliablyrecognizeacompromiseafterithasoccurred.Forexample,unexpectedserverbehaviorsuchasanoutboundconnectionunambiguouslyindicatessomecompromise.Thesystemcaninvokeavarietyofactionsinresponsetoalerts,including:–––––TemporarilyblockingtheaddressfromwhichanattackappearstooriginateIncreasingtheagreementregimeIncreasingthecoverageandfrequencyofthechallenge-responseprotocolDisconnectingandrebootingaserverRefusingserviceandalertingthesystemadministrator

Thechoiceofactiondependsonthecurrentsystemstateandthenatureofthealert.Alertscanbeevaluatedaccordingtotheseverityofthecompromisetheyindicate,thedetailtheyprovide,andthereliabilityofthealertitself.Wecon-siderthreeclassesofalerts:warningsofprobesandclearlyunsuccessfulattacks(detailed,reliable,butnotsevere),credibleindicationsthataspeci?cassetiscompromised(detailed,reliable,andsevere),andevidenceofsigni?cantattackswithunknownoutcome(notdetailed,somewhatreliable,andpotentiallysevere).Theresponsetoprobesandunsuccessfulattacksistotemporarilyblocktheapparentsourceaddress.Wearecarefulnottoblockfortoolong,sincethiscanleadtodenialofserviceifanattackerlaunchesanuisanceprobewithaspoofedsourceaddress.Ifanapplicationserverisdetectedascompromisedorotherwisefailed,thesystemadministratorisalerted,andtheserverisrebootedfromaread-onlycopyofitsoperatingsystemanddata.Theproxiesdetectthattheserverisbackonlinebyrunningaversionofthechallenge-responseprotocol.Theproxyrecoveryprotocolissimilar,withthedi?erencethattheoperationaldataforthe

168A.Valdesetal.

proxy(e.g.,currentpolicyandregime,con?guration)mustberecoveredfromtheotheroperationaltoleranceproxies,ifpresent.Adaptationisusedtorespondtothethirdclassofalerts.Theresponsetoevidenceofattackswithunknownoutcomeistomovetoamorestringentagreementregime,whichprovidesgreaterintegrityassuranceandhelpsidentifycompromisedservers.Thealertmanagerisaproxymodulethatacceptsalertsfromthemonitoringsubsystem.Itassessesthestateofeachapplicationserverasup,down,orsuspicious.Thisinformationisusedtochoosetheappropriateagreementregime,aspartoftheimplementedpolicy.Finally,somealertsarebothreliableandverysevere,andindicatethecom-promiseofasigni?cantnumberofcomponents.Suchalertsarise,forexample,ifthereisstillinsu?cientagreementafterallapplicationserversarequeried.Insuchcases,theonlysafeoptionistoshutdownthesystemandalertthesystemadministrator.Asanadditionalsecuritymechanism,serversandproxiesareregularlyre-bootedtopreventsoftwareaginganddefeatincrementalintrusions,asmentionedinSection3.3.Thisdoesnot?xany?awspresentinthesystem,butgivesanattackeronlyalimitedwindowoftimetoexploitthem.

4.4MultiproxyProtocols

Ourimplementationtodatehasfocusedondetectionandresponseprotocolsformultipleapplicationserversmediatedbyasingleleaderproxy,andnoauxiliaryones.However,wearedevelopingthegeneralcase,whereredundantproxiesmitigatetheweaknesspresentedbytheleaderasasinglepointoffailure(albeitahardenedandcloselymonitoredone).Inamultiproxycon?guration,auxiliaryproxiesmonitorrequestsandrepliesfromtheapplicationservers,andcanthusquicklyobserveiftheleaderhasfailed.Liketheleader,eachauxiliaryproxyincludesanalertmanager,whichreceivesreportsfromthemonitoringsubsystem.Adetectedfailureanywhereinthesystemisreportedtoallproxies,whichmustagreeontheresponse.Inparticular,theproxiesmustmaintainaconsistentviewofthecurrentregimeandofwhichproxyisthecurrentleader.Ourmultiproxydesignincludesthreeproxiesandisintendedtotoleratethecompromiseorfailureofoneofthem.Proxiescommunicatewitheachotherviaamulticastchannelimplementedusingalocalethernetlink(Figure1).Thischannelisassumedtoensurewithveryhighprobabilitythatanymessagefromoneproxyisdeliveredtoallotherproxies,andthatallmessagesarereceivedinthesameorderbyallproxies.Inparticular,thisguaranteesthatasymmetricfailures(afaultyproxysendinginconsistentmessagestoitspeers)donotoccur.Underthisassumption,simplemajorityvotingprotocolsaresu?cientformain-tainingconsistency.(Ifneeded,reliableatomicmulticastprotocols,suchas[25],canbeimplementedtosatisfythisassumption.)Whenaproxydecidesthatanewagreementregimeshouldbeenforced,itmulticastsarequesttotheotherproxies,whichreplybymulticastingtheir

AnArchitectureforanAdaptiveIntrusion-TolerantServer

169

Fig.3.High-levelviewofproxyimplementation

agreementordisagreement.Theregimeischangedonlyifatleasttwoofthethreeproxiesagree.Thedisagreeingproxy,ifany,isreportedtothealertmanagers.Ifanauxiliaryproxysuspectsthattheleaderisfaulty,itmulticastsarequestforchangingleader.Iftheotherauxiliaryproxyagrees,theleaderisdisconnectedforrepairandtheadministratorisalerted.Theproxythatinitiatedthechangeofleaderremainsauxiliaryandtheotherbecomesthenewleader.Iftheauxiliaryproxiesdisagreeontheleaderstatus,the“accuser”isconsideredsuspectbytheothertwo.Asimilarprotocolisusedifanauxiliaryproxyissuspectedofcompromise.Thedecisiontoexpelaproxy(leaderorauxiliary)requiresunanimitybetweenthetwoothers.Iftheydonotagree,theaccuserissuspectbutnotimmedi-atelyshutdown.Afteradelay,theaccusermaypersistandreinitiatetheexpelprotocol.Aftera?xednumberof“falseaccusations”,theaccuserisitselfcon-sideredfaultyandrestarted.Thisreducestheriskofprematurelyremovinganoncompromisedproxythataccusedanotherbymistake.

5Implementation

Ourinstantiationofthearchitectureprovidesintrusion-tolerantWebservices.The?rstprototypehasbeencompleted,focusingonthecontent-agreementpro-tocols,Webserverdeployment,andIDS.TheWebserversusedareApache1.3.20runningunderSolaris8andFreeBSD4.2,MicrosoftIIS5.0runningunderMSWindows2000,andNetscapeFastTrack4.1(iPlanet)underRedHat7.1.Figure3showsthemaincomponentsofourproxyimplementation.Theregimemanagerisresponsibleforexecutingthecontentagreementprotocol(Figure2).ThealertmanagertakesinputfromtheIDSsubsystemandthechallenge-reponseprotocols,andnoti?estheregimemanagerwhenchangesarewarranted.

170A.Valdesetal.

5.1MonitoringSubsystem

Theimplementedmonitoringsubsystemincludesavarietyofintrusiondetectionsensorsandalertcorrelationengines,asfollows:

–Network-basedsensorsdetectavarietyofnetworkattacksandprobesinrealtime.Thesesensorsrunonadedicatedmachinethatmonitorsthetra?cbetweentheclientsandtheproxy,andtheprivatesubnetbetweentheproxyandtheapplicationserverbank.eXpert-Netisasuiteofnetwork-basedsensors,eachofwhichfocusesonaspeci?cnetworkprotocol.Itfeaturesanattackknowledgebaseandinfer-enceenginedevelopedusingaforward-chainingrule-basedsystemgenera-tor,P-BEST[14].eXpert-Netcandetectcomplexattacksandvariationsofknownattacks.Forexample,byperformingsessionandtransactionrecon-struction,eXpert-HTTP,asensorformonitoringWebtra?c,detectsattacksthatwouldbemissediftheanalysiswereperformedonaper-packetbasis.Snort[26]isanopen-sourceintrusion-detectionsensorthathasanexten-siveandupdatedknowledgebaseofattacksignatures.AlthoughbothSnortandeXpert-Netaresignature-basedsensors,thediversityoftheirknowledgebasesandimplementationenablesthemtocomplementeachother.eBayes-TCP[29]usesaprobabilisticmodel-basedtechnique.Thiscombinesthegeneralizationpotentialofstatisticalanomalydetectionwiththeattackspeci?cityofsignature-baseddetection.–Host-basedoperating-system-levelsensorscomplementthenetwork-basedsensorsbymonitoringeventsattheoperatingsystemlevel.EMER-ALDeXpert-BSM[15]analyzestheauditrecordsgeneratedbytheSunSolarisBasicSecurityModule(BSM)toperformreal-timesignature-baseddetection.WeareinvestigatingdeployingSTAThost-basedmonitors[31]andRealSecuresensors[12]tomonitortheotheroperatingsystemplatforms,includingWindows.Thegeneratedalertsmustbeinacommonformat,suchasIDMEF[5],acceptedbythecorrelationengines.–Host-basedapplication-levelsensorscouplewithanapplicationtoobtainhigh-level,semanticallyrichdataforintrusion-detectionanalyses.WehavedevelopedanApachemoduletocollectHTTPtransactiondata,whichisanalyzedbythesignature-basedsensoreXpert-HTTP[1].–Abluesensor[29]discovershostsandservices,andmonitorstheiroper-ationalstatus,basedonBayesianinference.ThissensoriscoupledtotheEMERALDeBayes-TCPsessionmonitor.Asaresult,detectionsensitivityisincreased:failedaccessestoinvalidhostsandservicesareinherentlymoresuspicious.Moreover,falsealarmsarereduced:accessestounavailableser-vicesareexpectedtofail,soinnocenttra?caccessingtheseserviceswillnottriggeranalert.–AnEMERALDprobabilisticalertcorrelator[30]performsdatafusionfromheterogeneoussensors.

AnArchitectureforanAdaptiveIntrusion-TolerantServer171

5.2ContentAgreementUsingMD5Checksums

Abasicfunctionperformedbytheproxyischeckingthatthepagesreturnedbytwoormoreapplicationserversmatch.Toimprovethee?ciencyofthisprocess,weuseMD5checksums[24],whichtheserverscomputeforeachpageserved.Thesechecksumsarecryptographicallystrong:producingafakepagethatmatchesagivenMD5checksumisanintractableproblemgiventhecurrentandforeseeablestateoftheart.Whencomparingcontentfromseveralservers,onlytheMD5checksumsneedtoberetrievedfromallbutone,whichisqueriedforbothchecksumandcontent.Theproxyveri?esthatthechecksumsmatch;ifso,italsoveri?esthatthereceivedcontentmatchesthecommonMD5.Thishasthefollowingadvantages:–Internalnetworkbandwidthandproxymemoryrequirementsarereduced–Whenqueryingmultipleservers,itismoree?cienttocomparethechecksumsthanthefullnpages;verifyingasingleMD5isrelativelyinexpensive(linear-timeinpagesize)–Theleaderproxycankeepacacheofchecksums,tobecheckedwhenloweragreementregimesareused.Ifcachehitsoccur,theproxycanoperateatahigherassuranceleveldespiteusingfewerapplicationserversforcontent.TheservershaveallbeeninstrumentedtoincludetheMD5checksumheader,asspeci?edbyHTTP/1.1.TheApacheWebserverhasexperimentalsupportforMD5checksumheaders,whilethefeaturewasmanuallyaddedtobothiPlanetandIIS.TheMD5scouldbereplacedbyamoregeneralcryptographicsignature,whereeachapplicationserversignsitspagesusingauniqueprivatekey,andtheproxyveri?eseachofthesignatures.Suchasignaturecancertifythattheoriginofeachmessageisthecorrespondingapplicationserver,preventingspoo?ngontheprivatenetwork(whichcanalsobepreventedusingdedicatedhardware).Itdoesnot,however,guaranteetheintegrityofthecontentitself.Forinstance,ifsourcedata?lesarecompromisedbyanundetectedattack,theapplicationserverwillcorrectlysignthewrongdata.Similarly,public-keyinfrastructurecanbeusedsothattheend-users(clients)cancertifythattheoriginofaservedpageis,indeed,theproxyserver.Again,thismechanismbyitselfcannotguaranteetheintegrityofthecontent,butonlytheauthenticityofthesource.

5.3PolicyImplementation

OurimplementationsupportsavarietyofpoliciesbasedonageneralizationofthesimpleagreementregimesofExample1.Ingeneral,eachregimeisspeci?edbyapair(n,k),wherenisthenumberofserverstoquery,andkistheminimumnumberofserversthatyieldsu?cientagreementinthatregime.LetNbethenumberofapplicationservers,andPthesetofpairs(i,j),whereN≥i≥j≥1.Thepolicyisspeci?edbytwofunctions,start:{0,1,2,...}→Pandδ:P→P∪{panic}.IfthealertmanagerassessesthatFserversaresuspicious,then

172A.Valdesetal.

Table2.Asummaryofsecuritymechanismsintheproposedarchitecture–––Detectsunexpectedtra?coninternalnetworkTriggersadaptationmechanismsAlertssystemoperatorofseriousconditions

policies

–Detectserroneousapplicationserver(AS)behaviorlikelihoodofservingincorrectcontent–AvoidsqueryingsuspiciousandcompromisedAS–––TriggersadaptationmechanismsProvidesheartbeatforlivenesscheckRestrictscommunicationbetweenASandoutsideworld–RestrictsmanymalformedrequestsforwardedtoAS

accordingtospeci?cation

–Defeatslong-term,incrementalintrusions

proxiesandASstart(F)=(n,k)speci?estheinitialregime.Theclientrequestisforwardedtonservers,andaresponseisconsideredcorrectifthereisagreementbetweenkofthem;otherwise,thefunctionδisusedtoidentifyanewpair(n??,k??),whichdictatesthenewregime,queryingn???nextraservers.Thisisrepeateduntilsatisfactoryagreementisobtained,orthepanicstateisreached,inwhichcasethesystemisconsideredtoocorruptedtofunction.Thealertmanagerisnoti?edofthecontentagreementresults.

Implementedpoliciescanrangefrome?ciency-consciousonesthatinitiallyaskonlyafewserversandqueryoneadditionalserverwhenneeded,tointegrity-consciousonesthatquerymoreserversinitiallyandimmediatelyqueryallserverswhenindoubt.

6DiscussionandConclusions

Ourintrusion-tolerantarchitecturecombinesavarietyoftraditionalsecuritymechanisms,aswellasconceptsfromfaulttoleranceandformalveri?cation.Table2summarizesthesemechanisms,andtheprotectivefunctionstheyplay.Thesystemisadaptive,respondingtoalertsandintrusions,tradingo?perfor-

AnArchitectureforanAdaptiveIntrusion-TolerantServer173

manceagainstcon?denceintheintegrityoftheresults.Ourarchitectureallowsforawidevarietyofresponsepoliciestobeimplemented,dependingontheenvironmentalassumptionsandcost-bene?tanalysismade.

6.1AnExample—CodeRedScenario

Theutilityofthevariousmechanismsandlevelsofdetectionandrecoverycanbeillustratedusingthewell-knownCodeRedworm[17]asanexample.BoththeEMERALDeXpert-NetandSnortIDSspresentlyinstalleddetecttheCodeRedattack.Theproxiesarenoti?edofthedetection,andthesourceaddressoftheattackistemporarilyblocked.Considernowanattackthat,likeCodeRed,dependsonabu?erover?owincludedaspartoftherequest,butissu?cientlydi?erenttoevadethediverseIDS.Becauseofitslengthandunusualsyntax,theattackrequestislikelytobeblockedbytheproxy.Notethatahardenedproxy,compiledwithtoolssuchasStackGuard[2],shouldnotbevulnerabletogeneralbu?erover?owattacks.Supposenonethelessthattherequestisforwardedtotheapplicationservers.CodeRedwillonlya?ecttheIISservers,whichwillbeaminorityinadiversesystemimplementation.Theseserverswillbediagnosedasfailedandrestartedwhenerroneouscontentisfetchedfromthem,orasaresultofrunningthechallenge-responseprotocol.Meanwhile,theotherserversremainavailabletoprovidevalidcontent.WormssuchasCodeRedpropagatebyhijackingtheWebserverandinitiat-ingoutboundconnectionsfromtheserver.SuchconnectionsaredetectedbytheIDSontheprivatenetandblockedattheproxy,andthecorrespondingserverisdiagnosedasfailed.Insummary,theattackwouldhavetobypassanumberofmechanismstobesuccessful,includingdirectdetectionontheexternalnetwork,symptomdetec-tionontheprivatenetwork,failedagreement,andchallenge-responseprotocols.Themeansusedbytheattacktoinfectthesystem,corruptcontent,andprop-agatearee?ectivelythwarted.Moregenerally,webelievethatamultiplatformattackthatcancorruptcon-tentonamajorityofsu?cientlydiverseapplicationserversusingasinglequeryoractionisveryunlikely.Anattackthatexploitssimultaneouslypresentbutdi?erentvulnerabilitiesrequiresmoremalicioustra?c,increasingthelikelihoodofdetectionbyatleastonecomponent.

6.2DangersandTradeo?s

Acarelesslyimplementedandoverlyreactiveresponsepolicycancausethesys-temtooperatecontinuouslyatdegradedcapacity.Indeed,withsu?cientknowl-edgeofthedetectionandresponsemechanisms,anattackermaylaunchattackstotriggerresponsesthatresultinself-denialofservice.Asasimpleexample,itispossibletocraftanHTTPrequestthatwillmakedi?erentserverbrandsresponddi?erently,asdiscussedin[1].Replacingaregular

174A.Valdesetal.

space(ASCII20h)withthetabcharacter(09h)inaGETrequestyieldsavalidreplyfromtheApacheandtheiPlanetservers,butanerrorcodefromtheIISWebserver.Inthiscase,thereisnothingwrongwiththeIISserveranditshouldnotberebooted.Rather,theclientbehavessuspiciouslyandshouldbeblocked.AsmentionedinSection2.2,theproxyforwardsasanitizedversionoftheoriginalrequest.Thisincludeschangingallwhitespacestotheregularspace,soweavoidsuchattacks.

6.3RelatedWork

Anumberofcommercialproducts,suchasTripwireTMandEnterceptTM,concen-trateonprotectingstand-aloneWebservers,withnoredundancymanagement.Ourarchitecturecanusethesetechniquesasadditionalsecuritymeasures.SITAR[32]isanintrusion-tolerantarchitecturefordistributedservices,andsharesmanyofourgoalsandassumptions.Itincludesadaptiverecon?gura-tion,heartbeatmonitors,runtimechecks,andCOTSserversmediatedbyprox-ies.WhilewefocusontherelationshipbetweenIDSs,contentagreement,andadaptivepolicies,SITARfocusesonusingfault-tolerancetechniques,includingByzantineagreementprotocols,tocoordinatetheproxies.TheITUAproject[3]reliesonintrusiondetectionandrandomizedautomatedresponse.Itprovidesmiddlewarebasedonprocessreplicationandunpredictableadaptationtotoleratethefaultsthatresultfromstagedattacks.HACQIT[13]usesaprimary/backupserverarchitecturethatdoesnotperformcontentagree-ment,andfocusesonlearningbygeneralizingnewattacks.

AdaptiveFaultTolerance:Onemaincharacteristicofourarchitectureisitsabilitytoautomaticallyadapttheserverredundancytothelevelofalert.Mostfault-tolerantsystemsadapttheirredundancytocomponentfailures,ratherthanthelevelofperceivedthreat.Whenapersistentfaultisdiagnosed,thefaultyunitisisolated,repairedandthenreinserted.Inmostcases,thisdelayismadeasshortaspossibletomaintainasimilarlevelofredundancyforthewholemission.ArchitecturessuchasSIFT[33]andGUARDS[21],assigndi?erentlevelsofredundancytoconcurrenttasksaccordingtotheircriticality.Inotherfault-tolerantarchitecturessuchasDelta-4[22]andFRIENDS[8],di?erentredun-dancylevelsandtechniquesareassignedaccordingtofaultassumptionsratherthancriticality.Inthesearchitectures,aswellasinAQuA[4],theredundancylevelsassignedtotaskscanbemodi?edbyoperatorcommandstoadapttoenvironmentchanges.InSATURNE[7],idlecomputersareactivatedtoincreasetheredundancyofactivetasks,proportionallytotaskcriticality.Similarly,theAFTarchitecture[9]dynamicallyadaptsthetaskredundancyaccordingtotaskcriticalityandreal-timeconstraints.

6.4FutureWork

Weareworkingtowardsarationaltradeo?analysis,whichweseeasessen-tialtothedevelopmentofautomatedresponsemechanismsandtheireventual

AnArchitectureforanAdaptiveIntrusion-TolerantServer175

adoption.Choosingaresponsepolicyposesdi?culttradeo?sbetweenintegrity,availability,latency,andassumptionsaboutpotentialthreats.WewillstudytheapplicationofMarkovdecisionprocesstheorytothisproblem.Ourgoalisananalysisframeworkthatwillletusevaluatedi?erentpoliciesgivenavarietyofassumptionsaboutfaults,attacks,andaccuracyoftheIDSandmonitoringsubsystem.Wealsowanttoprovidemoreguaranteesconcerningtheabilityofthesystemtoavoidself-denialofserviceasaresultofalow-levelattack,aswellastheabilitytotolerateandrecoverfromadverseconditionsinatimelyfashion.Ourarchitectureshouldbemodi?edifalargenumberofapplicationserversareneeded.DiversityofCOTSimplementationisnotpracticalinthiscase.Instead,thearchitectureshouldbebasedonclusters,eachwithadiverseCOTSbaseandproxybank,replicatingthesingle-clustermodelthatwehavedescribed.Aloadmanagingcomponentbasedonourhardenedproxycanforwardeachquerytooneormoreclusters,dependingonthecurrentload.

Acknowledgments:WethankDanAnderssonandPhilPorrasfortheirfeed-backandcomments,andAydaSaidaneandVincentNicomettefortheircontri-butiontothechallenge-responseprotocol.

References

1.M.AlmgrenandU.Lindqvist.Application-integrateddatacollectionforsecuritymonitoring.InRecentAdvancesinIntrusionDetection(RAID2001),volume2212ofLNCS,pages22–36.Springer-Verlag,Oct.2001.2.C.Cowan,C.Pu,D.Maier,J.Walpole,P.Bakke,S.Beattie,A.Grier,P.Wagle,Q.Zhang,andH.Hinton.StackGuard:Automaticadaptivedetectionandpreven-tionofbu?er-over?owattacks.InProc.7thUSENIXSecurityConference,pages63–78,Jan.1998.3.M.Cukier,J.Lyons,P.Pandey,H.V.Ramasamy,W.H.Sanders,P.Pal,F.Web-ber,R.Schantz,J.Loyall,R.Watro,M.Atighetchi,andJ.Gossett.IntrusiontoleranceapproachesinITUA.InFastAbstractSupplementofthe2001Intl.Conf.onDependableSystemsandNetworks,pagesB–64,B–65,July2001.4.M.Cukier,J.Ren,C.Sabnis,D.Henke,J.Pistole,W.H.Sanders,D.E.Bakken,M.E.Berman,D.A.Karr,andR.Schantz.AQuA:anadaptivearchitecturethatprovidesdependabledistributedobjects.In17thIEEESymposiumonReliableDistributedSystems(SDRS-17),pages245–253.IEEEComputerSocietyPress,Oct.1998.5.D.CurryandH.Debar.Intrusiondetectionmessageexchangeformat:Datamodelandextensiblemarkuplanguage(XML)documenttypede?nition,Nov.2001.Workinprogress.6.Y.Deswarte,L.Blain,andJ.-C.Fabre.Intrusiontoleranceindistributedcomput-ingsystems.InProc.Intl.SymposiumonSecurityandPrivacy,pages110–121.IEEEpress,May1991.7.J.-C.Fabre,Y.Deswarte,J.-C.Laprie,andD.Powell.Saturation:Reducedidlenessforimprovedfault-tolerance.In18thInternationalSymposiumonFault-TolerantComputing(FTCS-18),pages200–205.IEEEComputerSocietyPress,1988.

176A.Valdesetal.

8.J.-C.FabreandT.P′erennou.Ametaobjectarchitectureforfault-tolerantdis-tributedsystems:TheFRIENDSapproach.IEEETransactionsonComputers,47:78–95,Jan.1998.9.O.Gonzalez,H.Shrikumar,J.Stankovic,andK.Ramamritham.Adaptivefaulttoleranceandgracefuldegradationunderdynamichardreal-timescheduling.In18thIEEEReal-TimeSystemsSymposium(RTSS’97).IEEEComputerSocietyPress,Dec.1997.10.G.J.Holzmann.DesignandValidationofComputerProtocols.PrenticeHall,EngelwoodCli?s,NJ,1991.11.Y.Huang,C.Kintala,N.Kolettis,andN.Fulton.Softwarerejuvenation:Analysis,moduleandapplications.In25thSymposiumonFaultTolerantComputing,pages381–390.IEEEComputerSocietyPress,June1995.12.RealSecureserversensorpolicyguideversion6.0,May2001..13.J.E.JustandJ.C.Reynolds.HACQIT(HierarchicalAdaptiveControlofQoSforIntrusionTolerance).In17thAnnualComputerSecurityApplicationsConference,2001.14.U.LindqvistandP.Porras.Detectingcomputerandnetworkmisusethroughtheproduction-basedexpertsystemtoolset(P-BEST).InProceedingsofthe1999IEEESymposiumonSecurityandPrivacy,pages146–161.IEEEpress,May1999.15.U.LindqvistandP.Porras.eXpert-BSM:Ahost-basedintrusiondetectionsolu-tionforSunSolaris.InProc.ofthe17thAnnualComputerSecurityApplicationsConference,Dec.2001.16.P.LiuandS.Jajodia.Multi-phasedamagecon?nementindatabasesystemsforintrusiontolerance.InProc.14thIEEEComputerSecurityFoundationsWorkshop,pages191–205,June2001.17.R.PermehandM.Mai?ret..ida“CodeRed”worm.SecurityAdvisoryAL20010717,eEyeDigitalSecurity,July2001./html/Research/Advisories/AL20010717.html.18.P.Porras.Mission-basedcorrelation.Personalcommunication,SRIInternational,2001.http://www./projects/M-correlation.19.P.PorrasandP.Neumann.EMERALD:EventMonitoringEnablingResponsestoAnomalousLiveDisturbances.InNationalInformationSecurityConference,Oct.1997.20.P.PorrasandA.Valdes.Livetra?canalysisofTCP/IPgateways.InProc.SymposiumonNetworkandDistributedSystemSecurity.InternetSociety,Mar.1998.21.D.Powell,J.Arlat,L.Beus-Dukic,A.Bondavalli,P.Coppola,A.Fantechi,E.Jenn,C.Rab′ejac,andA.Wellings.GUARDS:Agenericupgradablearchitectureforreal-timedependablesystems.IEEETransactionsonParallelandDistributedSystems,10:580–599,June1999.22.D.Powell,G.Bonn,D.Seaton,P.Ver′?ssimo,andF.Waeselynck.TheDelta-4approachtodependabilityinopendistributedcomputingsystems.InProc.18thInt.Symp.onFault-TolerantComputingSystems(FTCS-18),pages246–251.IEEEComputerSocietyPress,June1988.23.G.R.Ranger,P.K.Khosla,M.Bakkaloglu,M.W.Bigrigg,G.R.Goodson,S.Oguz,V.Pandurangan,C.A.N.Soules,J.D.Strunk,andJ.J.Wylie.Survivablestoragesystems.InDARPAInformationSurvivabilityConferenceandExpositionII,pages184–195.IEEEComputerSociety,June2001.24.R.Rivest.TheMD5messagedigestalgorithm.InternetEngineeringTaskForce,RFC1321,Apr.1992.

AnArchitectureforanAdaptiveIntrusion-TolerantServer177

25.L.RodriguesandP.Verissimo.xAMp:amulti-primitivegroupcommunicationsservice.In11thSymposiumonReliableDistributedSystems,pages112–121,Oct.1992.26.M.Roesch.Snort:Lightweightintrusiondetectionfornetworks.InUSENIXLISA’99,Nov.1999..27.F.B.Schneider.Enforceablesecuritypolicies.InformationandSystemSecurity,3(1):30–50,2000.28.Tripwirewhitepapers,2001..29.A.ValdesandK.Skinner.Adaptive,model-basedmonitoringforcyberattackdetection.InRecentAdvancesinIntrusionDetection(RAID2000),pages80–92,Oct.2000.30.A.ValdesandK.Skinner.Probabilisticalertcorrelation.InRecentAdvancesinIntrusionDetection(RAID2001),volume2212ofLNCS,pages54–68.Springer-Verlag,Oct.2001.31.G.Vigna,S.Eckmann,andR.Kemmerer.TheSTATtoolsuite.InDISCEX2000.IEEEpress,Jan.2000.32.F.Wang,F.Gong,C.Sargor,K.Goseva-Popstojanova,K.Trivedi,andF.Jou.SITAR:ascalableintrusiontolerancearchitecturefordistributedserver.InSecondIEEESMCInformationAssuranceWorkshop,2001.33.J.Wensley,L.Lamport,J.Goldberg,M.Green,K.Levitt,P.Melliar-Smith,R.Shostack,andC.Weinstock.SIFT:thedesignandanalysisofafault-tolerantcomputerforaircraftcontrol.Proc.IEEE,66:1240–1255,Oct.1978.

178

AnArchitectureforanAdaptiveIntrusion-TolerantServer(TranscriptofDiscussion)

VictoriaStavridou

SystemDesignLaboratory,SRIInternational

ErnieCohen:Ididn’tquiteunderstandwhatitisthatyou’remodelcheck-ing.Whatisthemodel?Reply:Weputtogetheranabstractionoftheproxy;whatitissupposedtobedoing.Thatisspeci?edasanautomaton.Thenyoucandoamodelcheckingthatveri?esthattheabstractionthatyouwanthastherighttemporal/liveness/safetyproperties.ThenyoucompilethosepropertiesintoblocksofCcode.Youthentakethecodeoftheproxywiththepropertiesthatareexpectedtobethereintheabstractionandthen,asyourun,youkeepexecutingthoseblockswhichwilltellyouifyou’redoingtherighttransitionsornot.ErnieCohen:Soitislikethealternativewaytodoit?Formostpoliciesyoucanjustwritethemasaregularexpression.Reply:Butrememberthisisnotpolicy,thesearepropertiestheproxyissupposedtohave.It’snotapolicy.RyoichiSasaki:Yourpaperisveryinteresting.Iwanttoknow,whenyoutalkaboutintrusion,whetherthismethodcanbeusedforthiswithacomputer?Reply:Ifyoulookatthepaper,thereisasectionthatdescribeshowwedefendagainstthat.OneoftheobviousthingstosayisthatyouwillknowthatsomethinghasgonewrongandblocktheURLoftheserverthatwillsendoutarequest.Eventhoughthatserverisinfected,nobadrequestwillevergobacktotheclient,therefore,althoughthethingitselfsu?ers,itdoesn’tpropagateanydamage.RogerNeedham:I?nditdi?culttobelievethatyouwouldeverbeabletogetreasonableprobabilityestimatesthataserverhasbeencompromised.Reply:Iagreeactually,Ithinkit’sthegoodold?ngerinthewind.Anon:Itwouldbewisetodowithout?ngersifyouarerunningsoftwarefromsomevendors.BruceChristianson:Let’snotgetintothequestionofhowmany?ngerswe’reholdingup.Theissueisthatsometimesyouendupwithapolicythat’sverysensitivetothoseparametervaluesandwhereasmallvariationinprobabilityleadstolargechanges.Clearlyifthatisn’tthecasethenitdoesn’tmattersomuch.