为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。
当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best to far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。
伪码表达：
procedure tabu search;
begin
initialize a string vc at random,clear up the tabu list;
cur:=vc;
repeat
select a new string vn in the neighborhood of vc;
if va>best_to_far then {va is a string in the tabu list}
begin
cur:=va;
let va take place of the oldest string in the tabu list;
best_to_far:=va;
end else
begin
cur:=vn;
let vn take place of the oldest string in the tabu list;
end;
until (termination-condition);
end;
以上程序中有关键的几点：
（1）禁忌对象：可以选取当前的值（cur）作为禁忌对象放进tabu list，也可以把和当然值在同一“等高线”上的都放进tabu list。
（2）为了降低计算量，禁忌长度和禁忌表的集合不宜太大，但是禁忌长度太小容易循环搜索，禁忌表太小容易陷入“局部极优解”。
（3）上述程序段中对best_to_far的操作是直接赋值为最优的“解禁候选解”，但是有时候会出现没有大于best_to_far的，候选解也全部被禁的“死锁”状态，这个时候，就应该对候选解中最佳的进行解禁，以能够继续下去。
（4）终止准则：和模拟退火，遗传算法差不多，常用的有：给定一个迭代步数；设定与估计的最优解的距离小于某个范围时，就终止搜索；当与最优解的距离连续若干步保持不变时，终止搜索；
禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的.
遗传算法是基于生物进化的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。
蚂蚁算法是群体智能可用于解决其他组合优化问题,比如有n个城市，需要对所有n个城市进行访问且只访问一次的最短距离。
2008-06-25
2008-06-24
TU CIS / ISec companies
http://meketrex.com/
http://www.linkedin.com/pub/4/533/0B7 David Greer
http://www.truedigitalsecurity.com/ Jerald Dawkins
http://www.okdfp.com/ Digital Forensics Professionals
Gavin Maine
http://www.linkedin.com/pub/4/533/0B7 David Greer
http://www.truedigitalsecurity.com/ Jerald Dawkins
http://www.okdfp.com/ Digital Forensics Professionals
Gavin Maine
2008-06-23
Automated Debugging (6): simplifying problems - smiple testcase for complex bug repor
need some more time for each of the left chapters
1. Main points
* The aim of simplification is to create a simple test case from a problem report.
* Simplified test cases…
*** are easier to communicate
*** facilitate debugging
*** identify duplicate problem reports
* To simplify a test case, remove all irrelevant circumstances.
* A circumstance is irrelevant if the problem occurs regardless of whether the circumstance is present or not.
* To automate simplification, set up
*** an automated test
*** a strategy to determine the relevant circumstances
One such strategy is the ddmin delta debugging algorithm
ZW Comment: ddmin is a great idea, but seems to be not that general to be used in every scenarios
(in fact, my current thought is that its application domain is not that broad, anyway the simple failure-inducing input in the given example is not that common in practice).
Some more examples where ddmin might be useful:
* Simplified failure-inducing fuzz input:
* FLEX crashes on 2,121 or more non-newline characters
* NROFF crashes on “\D^J%0F” or “\302\n”
* CRTPLOT crashes on “t”
The algorithm complexity analysis is out of my expectation. As I thought, the space is 2^M (might be a good target for GA :-), but the author give an algorithm whose worst case is (|c| ^ 2 + 7 * c) / 2.
Hehe, I guess there might be some corner of this space is not covered by his method.
Need some more look.
1. Main points
* The aim of simplification is to create a simple test case from a problem report.
* Simplified test cases…
*** are easier to communicate
*** facilitate debugging
*** identify duplicate problem reports
* To simplify a test case, remove all irrelevant circumstances.
* A circumstance is irrelevant if the problem occurs regardless of whether the circumstance is present or not.
* To automate simplification, set up
*** an automated test
*** a strategy to determine the relevant circumstances
One such strategy is the ddmin delta debugging algorithm
ZW Comment: ddmin is a great idea, but seems to be not that general to be used in every scenarios
(in fact, my current thought is that its application domain is not that broad, anyway the simple failure-inducing input in the given example is not that common in practice).
Some more examples where ddmin might be useful:
* Simplified failure-inducing fuzz input:
* FLEX crashes on 2,121 or more non-newline characters
* NROFF crashes on “\D^J%0F” or “\302\n”
* CRTPLOT crashes on “t”
The algorithm complexity analysis is out of my expectation. As I thought, the space is 2^M (might be a good target for GA :-), but the author give an algorithm whose worst case is (|c| ^ 2 + 7 * c) / 2.
Hehe, I guess there might be some corner of this space is not covered by his method.
Need some more look.
2008-06-22
Automated Debugging (5): reproducing problems - better than what I had thought
1. Why reproduce?
* Observing the problem. Without being able to reproduce the problem, one cannot observe it or find any new facts.
* Check for success. How do you know that the problem is actually fixed?
2. Reproducing is Tough
* Reproducing is one of the toughest problems in debugging.
* One must recreate the environment in which the problem occurred
* also need to recreate the problem history – the steps that lead to the problem
3. Reproducing the Environment
* Iterative Reproduction
* Start with your environment
* While the problem is not reproduced, adapt more and more circumstances from the user’s environment
* Iteration ends when problem is reproduced (or when environments are “identical”)
* Side effect: Learn about failure-inducing circumstances
4. Reproducing Execution
* Basic idea: Any execution is determined by the input (in a general sense)
* Reproducing input → reproducing execution!
4.1 data
* Easy to transfer and replicate
* Caveat #1: Get all the data you need
* Caveat #2: Get only the data you need
* Caveat #3: Privacy issues
4.2 User interaction
Record and Replay
4.3 Communication
* General idea: Record and replay like user interaction
* Bad impact on performance
* Alternative #1: Only record since last checkpoint (= reproducible state)
* Alternative #2: Only record “last” transaction
ZW comments: not sure what the alternatives mean.
4.4 Randomness
* Program behaves different in every run
* Based on random number generator
* Pseudo-random: save seed (and make it configurable): Same applies to time of day
* True random: record + replay sequence
4.5 Operating System
* The OS handles entire interaction between program and environment
* Recording and replaying OS interaction thus makes entire program run reproducible
* Trace the program and replay the trace
* Trace Challenges
Tracing creates lots of data
Example: Web server with 10 requests/sec A trace of 10 k/request means 8GB/day
All of this must be replayed to reproduce the failure (alternative: checkpoints)
Huge performance penalty!
4.6 Scheduling
* Thread changes are induced by a scheduler
* It suffices to record the schedule (i.e. the moments in time at which thread switches occur) and to replay it
* Requires deterministic input replay
Constructive Solutions
* Lock resource before writing
* Check resource update time before writing
* ... or any other synchronization mechanism
4.7 Physical Influences
Rare and hard to reproduce
* Static electricity
* Alpha particles (not cosmic rays)
* Quantum effects
* Humidity
* Mechanical failures + real bugs
4.8 Debugging Tools
* Heisenbug: Code fails outside debugger only
* Bohr Bug, Mandelbug, Schrödinbug
Bohr Bug = Repeatable under well-def’d conditions
Heisenbug = Changes when observed
Mandelbug = Causes are complex and chaotic, appears non-deterministic, but isn’t
Schrödinbug = Never should have worked, and promptly fails as soon one realizes this
5. Isolating Units
* Capture + replay unit instead of program
* Needs an unit control layer to monitor input
Examples:
* Databases. Replay only the interaction with the database.
* Compilers. Record + replay intermediate data structures rather than the entire front-end.
* Networking. Record + replay communication calls.
More Interaction
* Variables (hard to detect)
* Other units (break dependency if needed)
* Time (record + replay, too)
*
*
* Observing the problem. Without being able to reproduce the problem, one cannot observe it or find any new facts.
* Check for success. How do you know that the problem is actually fixed?
2. Reproducing is Tough
* Reproducing is one of the toughest problems in debugging.
* One must recreate the environment in which the problem occurred
* also need to recreate the problem history – the steps that lead to the problem
3. Reproducing the Environment
* Iterative Reproduction
* Start with your environment
* While the problem is not reproduced, adapt more and more circumstances from the user’s environment
* Iteration ends when problem is reproduced (or when environments are “identical”)
* Side effect: Learn about failure-inducing circumstances
4. Reproducing Execution
* Basic idea: Any execution is determined by the input (in a general sense)
* Reproducing input → reproducing execution!
4.1 data
* Easy to transfer and replicate
* Caveat #1: Get all the data you need
* Caveat #2: Get only the data you need
* Caveat #3: Privacy issues
4.2 User interaction
Record and Replay
4.3 Communication
* General idea: Record and replay like user interaction
* Bad impact on performance
* Alternative #1: Only record since last checkpoint (= reproducible state)
* Alternative #2: Only record “last” transaction
ZW comments: not sure what the alternatives mean.
4.4 Randomness
* Program behaves different in every run
* Based on random number generator
* Pseudo-random: save seed (and make it configurable): Same applies to time of day
* True random: record + replay sequence
4.5 Operating System
* The OS handles entire interaction between program and environment
* Recording and replaying OS interaction thus makes entire program run reproducible
* Trace the program and replay the trace
* Trace Challenges
Tracing creates lots of data
Example: Web server with 10 requests/sec A trace of 10 k/request means 8GB/day
All of this must be replayed to reproduce the failure (alternative: checkpoints)
Huge performance penalty!
4.6 Scheduling
* Thread changes are induced by a scheduler
* It suffices to record the schedule (i.e. the moments in time at which thread switches occur) and to replay it
* Requires deterministic input replay
Constructive Solutions
* Lock resource before writing
* Check resource update time before writing
* ... or any other synchronization mechanism
4.7 Physical Influences
Rare and hard to reproduce
* Static electricity
* Alpha particles (not cosmic rays)
* Quantum effects
* Humidity
* Mechanical failures + real bugs
4.8 Debugging Tools
* Heisenbug: Code fails outside debugger only
* Bohr Bug, Mandelbug, Schrödinbug
Bohr Bug = Repeatable under well-def’d conditions
Heisenbug = Changes when observed
Mandelbug = Causes are complex and chaotic, appears non-deterministic, but isn’t
Schrödinbug = Never should have worked, and promptly fails as soon one realizes this
5. Isolating Units
* Capture + replay unit instead of program
* Needs an unit control layer to monitor input
Examples:
* Databases. Replay only the interaction with the database.
* Compilers. Record + replay intermediate data structures rather than the entire front-end.
* Networking. Record + replay communication calls.
More Interaction
* Variables (hard to detect)
* Other units (break dependency if needed)
* Time (record + replay, too)
*
*
Design for Debugging
1. A good point from studying AD series (3)
Google Search
Semantic issues in the design of languages for debugging
PPP Design and Debugging
Design-for-debugging of application specific designs
Design for Debugging, Test, or Both
Design-for-Debug: A Vital Aspect in Education
Design Time Debugging during server control development in asp.net2.0 in Visual Studio 2005
Google Search
Semantic issues in the design of languages for debugging
PPP Design and Debugging
Design-for-debugging of application specific designs
Design for Debugging, Test, or Both
Design-for-Debug: A Vital Aspect in Education
Design Time Debugging during server control development in asp.net2.0 in Visual Studio 2005
Automated Debugging (4): making problems fail - automated test for debugging
mainly talk about testing, from the point of view helping debugging
1. Overview
1) To test for debugging, one must...
* create a test to reproduce the problem
* run the test several times during debugging, and
* run the test before new releases to prevent regression
2) Automate as much as possible
3) To test at the presentation layer, simulate human interaction
4) To test at the functionality layer, use an automation interface
5) To test units, use the unit API to control it and assess its results
6) To isolate a unit, break dependencies using the dependency inversion principle
7) To design for debugging, reduce the amount of dependencies
8) A variety of techniques is available to prevent errors and problems
ZW comment 1: design for debugging is the interesting concept...Some more exploration
ZW comment 2: Memory past
1) dogtail for Frysk GUI test: Link to the author
2) JUnit test work in Amino team, parallel extension for JUnit
The amino project
http://amino-cbbs.blogspot.com/
1. Overview
1) To test for debugging, one must...
* create a test to reproduce the problem
* run the test several times during debugging, and
* run the test before new releases to prevent regression
2) Automate as much as possible
3) To test at the presentation layer, simulate human interaction
4) To test at the functionality layer, use an automation interface
5) To test units, use the unit API to control it and assess its results
6) To isolate a unit, break dependencies using the dependency inversion principle
7) To design for debugging, reduce the amount of dependencies
8) A variety of techniques is available to prevent errors and problems
ZW comment 1: design for debugging is the interesting concept...Some more exploration
ZW comment 2: Memory past
1) dogtail for Frysk GUI test: Link to the author
2) JUnit test work in Amino team, parallel extension for JUnit
The amino project
http://amino-cbbs.blogspot.com/
Automated Debugging (3): tracking the problems - bugzilla
1. What is a problem?
* A problem is a questionable property of a program run
* It becomes a failure if it’s incorrect...
* ...a request for enhancement if missing...
* ......and a feature if normal behavior.
......As some body says: It’s not a bug, it’s a feature! :-)
2. Problem Life Cycle
User / Tester reports it
Vendor / Programmer reproduce it; isolate the circumstances; locate and fix the defects; deliver the fix to user/tester
3. Vendor / User Challenges
Vendor:
* How do I organize the life cycle?
* Which problems are currently open?
* Which are the most severe problems?
* Did similar problems occur in the past?
User:
* Solve my problem!
4. Problem Report / Bug Report / Change Request
* A problem comes to life with a problem report.
* A problem report includes all the information the vendor needs to fix the problem.
* Also known as change request or bug report.
Bad report examples:
* only a description
* a core dump, no circumstance
* zip of hard drive image
What to report
* The product release
* The operating environment
* The problem history
* Expected and experienced behavior
* A one-line summary
ZW's comment:......Maybe a process description is needed: the setup, the process to reproduce (or spontaneous...)?
Memory of my earlier days in IBM R&D center:
After a quick go-thru of the slides, it reminds me of the first two years' work in IBM. RHEL / SLES testers: IO, FileSystem, Networking and many other work. Problem Determination...... and so on.....
* Daily Life with Bugzilla as my homepage
* The most productive bug reporter, and the promotion to problem determiner
* Report a handful of kernel bugs...
* Solved three of them, given credit...... Pride and Dream... You can spend some time to find and write them down
* PIG CAN RIDE!!!...Ladies riding a pig on youtube~~~~~~ :-)
* Journey to Austin, TX...... Many first-time experiences......Many long sighs...
* Many more......
Many other funny videos about pig riding on youtube:~~~~~
* Pig riding and skateboard
* Other pig riding videos
An interesting point here is that Talk-Back Style Bug Reporting and Privacy.... People are very concerned with their privacy nowadays anyway.
* A problem is a questionable property of a program run
* It becomes a failure if it’s incorrect...
* ...a request for enhancement if missing...
* ......and a feature if normal behavior.
......As some body says: It’s not a bug, it’s a feature! :-)
2. Problem Life Cycle
User / Tester reports it
Vendor / Programmer reproduce it; isolate the circumstances; locate and fix the defects; deliver the fix to user/tester
3. Vendor / User Challenges
Vendor:
* How do I organize the life cycle?
* Which problems are currently open?
* Which are the most severe problems?
* Did similar problems occur in the past?
User:
* Solve my problem!
4. Problem Report / Bug Report / Change Request
* A problem comes to life with a problem report.
* A problem report includes all the information the vendor needs to fix the problem.
* Also known as change request or bug report.
Bad report examples:
* only a description
* a core dump, no circumstance
* zip of hard drive image
What to report
* The product release
* The operating environment
* The problem history
* Expected and experienced behavior
* A one-line summary
ZW's comment:......Maybe a process description is needed: the setup, the process to reproduce (or spontaneous...)?
Memory of my earlier days in IBM R&D center:
After a quick go-thru of the slides, it reminds me of the first two years' work in IBM. RHEL / SLES testers: IO, FileSystem, Networking and many other work. Problem Determination...... and so on.....
* Daily Life with Bugzilla as my homepage
* The most productive bug reporter, and the promotion to problem determiner
* Report a handful of kernel bugs...
* Solved three of them, given credit...... Pride and Dream... You can spend some time to find and write them down
* PIG CAN RIDE!!!...Ladies riding a pig on youtube~~~~~~ :-)
* Journey to Austin, TX...... Many first-time experiences......Many long sighs...
* Many more......
Many other funny videos about pig riding on youtube:~~~~~
* Pig riding and skateboard
* Other pig riding videos
An interesting point here is that Talk-Back Style Bug Reporting and Privacy.... People are very concerned with their privacy nowadays anyway.
订阅：
博文 (Atom)
