However, I should briefly clarify Paul’s note that “blackboard systems historically used a single memory model (i.e. multiple threads or processes using a single machine’s memory model)“.

In fact, there were many blackboard systems, some more than a decade old, that used a distributed memory data-model. What I think Paul meant to say, and my apologies to Paul for being so literal, is that “blackboard systems originally used a single memory model (i.e. multiple threads or processes using a single machine’s memory model)”

John McManus, former CTO of NASA, wrote an excellent PhD dissertation in 1992, Design and Analysis Techniques for Concurrent Blackboard Systems. John’s thesis, now more than 16 years old, examined many details of concurrent blackboards where memory is distributed. For example, refer to Figure 2.3. Distributed Blackboard System with Distributed Blackboard Data Structure, page 36 of John’s dissertation.

Quoting directly from page 37 of John’s disseration;

Rice, Aiello and Nii [20] present several options for gaining speedups in a distributed blackboard system.

• 1) Eliminate the centralized scheduling mechanism
• 2) Optimize system design for a distributed memory, message-passing hardware
• 3) Distribute the data across the blackboard to reduce hotspots

Quoting further from the same page;

Poligon [21] is based on a distributed memory hardware model when each processor is viewed as a blackboard node. They define a blackboard node as follows: “a blackboard node is a process on a processor, surrounded by a collection of processors able to service its requests to execute rules.” [22] The implicit assumption in this definition is that all knowledge sources are rule–based systems. This assumption may severely limit the performance of systems implemented using Poligon, and limits the types of problems it is suited to address.

In Blackboards for Complex Event Processing, Paul concludes,

“One suspects the blackboard systems domain and terminology is overdue some updates thanks to developments in the Complex Event Processing space.”

If you look at the historical literature, I would say that the following restatement is more accurate:

“The CEP domain and terminology is overdue some updates because folks working in CEP did not reference or incorporate the advanced event processing prior art in a number of very important areas, blackboard systems being only one.”

On the other hand, commercial off-the-shelf rule-processing technology such as TIBCO’s BusinessEvents (BE), advances the ability to economically implement myriad complex problems that blackboard systems are designed to address.

Complex event processing (CEP) is a new technology. It can be applied to extracting and analyzing information from any kind of distributed message-based system. It is developed from the Rapide concepts of (1) causal event modeling, (2) event patterns and pattern matching, and (3) event pattern maps and constraints. Complex event processing can be applied to a wide variety of Enterprise monitoring and management problems, from low level network management to high level enterprise intelligence gathering.

Applications of Complex Event Processing:

• Instant Insight  - hierarchical event viewing applied to the Enterprise IT layer. (coming soon)
  • Analysing business processes (paper in pdf format)
• Network Level Monitoring and Management (Powerpoint presentation)
• Cyber Security: Network Intrusion Detection
• Enterprise Monitoring and Management (coming soon)
• Modeling and Simulation of Collaborative Business Processes
• Business Policy Monitoring. (coming soon)
• Analysis and Debugging of Distributed Systems (coming soon)

Presentations:

• “Complex Event Processing: An Essential Technology for Instant Insight into the Operation of Enterprise Information Systems,” lecture at the Stanford University Computer Systems Laborary EE380 Colloquium series. Video of the lecture (duration: 60 minutes).

Publications:

• Complex Event Processing in Distributed Systems. David C. Luckham and Brian Frasca, Stanford University Technical Report CSL-TR-98-754, March 1998, 28 pages.Abstract: Complex event processing is a new technology for extracting information from distributed message-based systems. This technology allows users of a system to specify the information that is of interest to them. It can be low level network processing data or high level enterprise management intelligence, depending upon the role and viewpoint of individual users. And it can be changed from moment to moment while the target system is in operation. This paper presents an overview of Complex Event Processing applied to a particular example of a distributed message-based system, a fabrication process management system. The concepts of causal event histories, event patterns, event filtering, and event aggregation are introduced and their application to the process management system is illustrated by simple examples. This paper gives the reader an overview of Complex Event Processing concepts and illustrates how they can be applied using the Rapide toolset to one specific kind of system.
   
• Event Mining with Event Processing Networks. Louis Perrochon and Walter Mann and Stephane Kasriel and David C. Luckham, The Third Pacific-Asia Conference on Knowledge Discovery and Data Mining. April 26-28, 1999. Beijing, China, 5 pages.Abstract: Event Mining discovers and delivers information and knowledge in a real-time stream of data, or events. We show that the process of delivering knowledge by searching patterns in data and subsequent abstraction of found patterns can be applied in real-time to a complex, asynchronous system. Our event processing engine consists of a network of event processing agents (EPAs) running in parallel that interact using a dedicated event processing infrastructure. The agents can be configured at run-time using a formal pattern language. The underlying infrastructure (1) provides an abstract communication mechanism and thus allows dynamic reconfiguration of the communication topology between agents at run-time and (2) provides transparent, location-independent access to all data. These features allow dynamic allocation of EPAs to different threads and processes on different machines at run time.
   
• eJava - Extending Java with Causality. Alexandre Santoro and Walter Mann and Neel Madhav and David Luckham, Proceedings of the 10th International Conference on Software Engineering and Knowledge Engineering, June 1998, 10 pages.Abstract: Programming languages like Java provide designers with a variety of classes that simplify the process of program development. Some of these classes allow one to easily build multithreaded programs. Though useful, especially in the creation of reactive systems, multithreaded programs present challenging problems such as race conditions and synchronization issues. Validating these programs against a specification is not trivial since Java does not clearly indicate thread interaction. These problems can be solved by modifying Java so that it produces computations, collections of events with both causal and temporal ordering relations defined for them. Specifically, the causal ordering is ideal for identifying thread interaction. This paper presents eJava, an extension to Java that is both event based and causally aware, and shows how it simplifies the process of understanding and debugging multithreaded programs.
   
• Event-Based Execution Architectures for Dynamic Software Systems. James Vera, Louis Perrochon, David C. Luckham.
  Proceedings of the First Working IFIP Conf. on Software Architecture. 1999. San Antonio, Texas.Abstract: Distributed systems’ runtime behavior can be difficult to understand. Concurrent, distributed activity make notions of global state difficult to grasp. We focus on the runtime structure of a system, its execution architecture, and propose representing its evolution as a partially ordered set of predefined architectural event types. This representation allows a system’s topology to be visualized, analyzed and con-strained. The use of a predefined event types allows the execution architectures of different systems to be readily compared.
   
• Using Context-Based Correlation in Network Operations and Management. Louis Perrochon (work in progress, mail author for newest version)Abstract: Network operation consists to a large degree of reaction to activities happening in the network. Better knowledge of the network at any time allows more appropriate reactions. On the example of intrusion detection, we show how context-based correlation of such activities can provide a more detailed view of the network in shorter time. We first present how we model context and then describe the architecture of the Stanford University CEP context-based correlator. Correlation is specified as event patterns in a declarative language that allows us to specify what needs to be detected, instead of specifying how it should be detected. CEP introduces the concept of causal context to intrusion detection. The correlator is able to process events on-line, as they are generated and it can be reconfigured at dynamically. We then show how it increases detection rate, reduce false alarms, and detect large-scale attack patterns at an early stage.

A while back I wrote about how much I liked the Xobni email add on for Outlook. A short time later I heard rumors that Microsoft was buying them, but that appears not to be true at this point, though I still think it makes a lot of sense.  In the meantime, I have continued to use and be impressed with Xobni.  I have come to rely on its ultra fast search and the way it organizes threads of conversations and groups of people, as well as attached files.

An interesting thing though about Xobni. As I was given invitations, I would send them out to people I know.  Though many of them liked the functionality of the product, they said that it slowed their Outlook to a crawl and just did not think the performance hit was worth it.  Maybe I got used to the slowness or I am just not seeing it, but I did not see what they saw. In any event, many people were not using the product.

Well the Xobni folks just released a new version of the product that promises improved performance. I hope that helps those people who were complaining about this. It also offers several other new features, the biggest being LinkedIn integration.  I really like this LinkedIn integration as it gives you yet another layer of information on the people writing to you. All in all, I think this just makes the product more indispensable than it is already.  It is now available to the public, so I would encourage you to check it out for yourself!

A while back I wrote about how much I liked the Xobni email add on for Outlook. A short time later I heard rumors that Microsoft was buying them, but that appears not to be true at this point, though I still think it makes a lot of sense.  In the meantime, I have continued to use and be impressed with Xobni.  I have come to rely on its ultra fast search and the way it organizes threads of conversations and groups of people, as well as attached files.

An interesting thing though about Xobni. As I was given invitations, I would send them out to people I know.  Though many of them liked the functionality of the product, they said that it slowed their Outlook to a crawl and just did not think the performance hit was worth it.  Maybe I got used to the slowness or I am just not seeing it, but I did not see what they saw. In any event, many people were not using the product.

Well the Xobni folks just released a new version of the product that promises improved performance. I hope that helps those people who were complaining about this. It also offers several other new features, the biggest being LinkedIn integration.  I really like this LinkedIn integration as it gives you yet another layer of information on the people writing to you. All in all, I think this just makes the product more indispensable than it is already.  It is now available to the public, so I would encourage you to check it out for yourself!

The reporter notes other common threads of problems with metro-scale networks: lowballed budgets, which turned out to underestimate infrastructure costs (nodes, real-estate rights, utility pole issues), low demand, and weak signals inside homes. Tempe apparently had 1,000 subscribers at one point, in a city of 166,000 (2005 census estimate).

The articles states, "The upside is Tempe and other Valley cities didn't spend taxpayer dollars." Of course, as I've noted before, the idea with a wireless network should be to both conserve expenses and reduce them. "Taxpayer dollars" is a shibboleth of those who believe government can solve no ills. Those who believe that are typically also fine with government overspending by paying large companies as private contractors rather than working in a public/private partnership that reduces expenses and yet puts most dollars into the private sector--just in smaller firms.

Gilbert, Ariz., one of several Arizona cities that was contracted with Kite, reaches fifth stage of mourning, acceptance: Gobility, Kite's ostensibly current owner, hasn't communicated with the city in two months, and its elusive head wouldn't comment for this article in local paper. The city isn't too depressed.

Oklahoma City is OK with lack of Wi-Fi network for public access: They're pretty pleased with their large mesh network for emergency services.

Last week at RSA, Microsoft Chief Research and Strategy Officer Craig Mundie spoke and outlined a proposed vision for “End to End Trust.” Much has and will be written on that, and additional information and discussions can be found at the End to End Trust portal http://www.microsoft.com/endtoendtrust. In many ways, Craig’s talk was very unusual for Microsoft’s presence at RSA in that it wasn’t a big new product announcement, nor was it evangelizing a new technology or platform to innovate upon. Rather, it was a aimed at kicking off a dialogue by describing some of the current challenges and barriers we see to achieving a more trusted and privacy enhanced Internet, and some of our ideas on how both industry and society might be able to start a productive dialog about collaborating toward that end.    Make no mistake: this is tough stuff. This needs to be an industry-wide, long-term effort, and it’s about more than just technology. Enabling true End to End Trust will require that we continue to build on technology progress while aligning those innovations more closely with social, economic and political forces.

Along those lines, I wanted to take a few moments and comment on how SDL factors into that broader discussion on trust. Allow me to draw some analogies with some of my prior work…

In the late 1990’s, I was not yet working on computer security but on computer speech recognition and speech synthesis for Microsoft. Having an engineering background, I was (and still am) very interested in the opportunities and possibilities enabled by freeing people from computer keyboards and mice and allowing them to interact with computers in one of the same ways we interact with each other – by voice. Speech recognition was, and still is, largely assessed by a key metric of “what percentage of words spoken by a person did the computer correctly understand?” Nirvana for speech recognition is 100 percent accuracy (defined as “the computer correctly understood all of the words spoken”) with any audio stream (even with a microphone far away from a person in a noisy room) with an unlimited vocabulary (regardless if I am discussing sports using slang or detailed technical terminology) in any spoken language/dialect. State of the art of speech recognition technology today is not 100 percent accurate within the parameters I described, but let’s pretend for a minute that it is – then what? If you start thinking more deeply on this subject, you can quickly see that many other pieces of the puzzle are needed to realize the goal of “allowing people to interact with computers in one of the same ways we interact with each other – by voice. Natural Language Processing and designing an effective Voice User Interface (VUI) are two of the first major challenges encountered when trying to realize the broader vision of enabling people to interact with computers via voice. These are hard problems that I hope to see significant progress on in my lifetime. However, analyzing an audio stream and converting into some format (words or otherwise) is a fundamental requirement necessary for speech recognition. Yet, it’s also insufficient to realize the broader vision.

Some of you reading may be thinking “But wait Eric, this is a security blog so why are you rambling on about your former roles working on speech recognition?” Well, there is an analogy I’m trying to draw. The point I’ve been leading up to is that the SDL plays a similar role in the context of realizing the broader “End to End Trust” vision. Having software that operates securely without exposing systems or data to unnecessary risk is a fundamental requirement in order for people to trust their computers and software. Yet, that alone is insufficient to enable confidence and trust. As Scott Charney noted in the “End to End Trust Paper:”

“There remained, however, other more specific threats not well addressed by SD3 or Defense-in-Depth. For example, spam does not normally exploit vulnerabilities, nor would one turn off mail by default. There is also very little a specific user or enterprise can do to prevent a distributed denial-of service attack from a botnet. As a result, Microsoft started working on threat mitigations for specific issues. With regard to phishing and spam, for example, it engaged in broad consumer education campaigns and worked on developing technological solutions such as phishing filters and SenderID. For both phishing and botnets, Microsoft began working more extensively with law enforcement to identify phishers and botnet herders in an attempt to create deterrent to such activity, even though the deterrent effect is limited by the current environment because it is hard to find offenders, and criminal penalties may be applied without sufficient force.”

In the non-computing world, even if I keep my house, car, and other valuables under lock and key, I still am at risk of being victimized by criminal activity through no fault of my own. However, a broader set of societal constructs help offer improved assurances that if I don’t live careless or recklessly I will largely remain safe and secure. Note I said “improved.” Society is still not perfect; crime still exists and it always will! The online world is no different. The online world has not yet been around quite as long as human society, it too needs help in developing improved assurances – assurances that ensure I will largely remain safe and secure given I don’t live carelessly or recklessly. These assurances can’t be provided by any single vendor. They require collaboration from all of industry, and indeed society. Craig Mundie’s talk aimed to start a dialogue about how to evolve our online society to be a safer place, where devices and software enable people to make more effective trust decisions and take control over whom and what they trust online.

The creation of a more trustworthy Internet will benefit all of society, and an open dialogue among its members is critical component of achieving this. Feel free to go to http://forums.community.microsoft.com/en-US/EndToEndTrust/threads/ and chime in with your thoughts. As Scott Charney noted “"… if we want the internet to reach its full potential, we need a safer, more trusted online environment."

Previously, James Whittaker posted a blog entry on Testing in the SDL in which he mentioned that many folks equate fuzz testing with security testing.  While fuzz testing doesn't come close to describing how security testing is done at Microsoft it does happen to be one of our most scalable testing approaches to detecting program failures that may have security implications. 

As Michael Howard has pointed out before, we do our best to ensure that the SDL incorporates lessons learned from vulnerabilities that required us to release security updates.  It turns out that the animated cursor bug patched in MS07-017 had a positive impact on the automatic triaging our fuzz testing tools perform.  In this post, I'd like to shed some light on how we monitor for program failures when fuzzing parsers and how the recent animated cursor bug, MS07-017 caused us to revisit and ultimately improve our fuzzing tools.

Background

For our purposes, fuzz testing is a method for finding program failures (code errors) by supplying malformed input data to program interfaces (entry points) that parse and consume this data (e.g. file, network, registry, shared memory parsers).  At Microsoft, we view fuzz testing as six distinct stages in which the output of each stage can impact or influence both the current and next iteration through the stages (e.g. after completing analysis work in stage 5 you could decide to change how you malform and deliver fuzzed data [stage 2 and 3], which exceptions get logged [stage 4], which tests you re-run [stage 6] and even which parsers you might decide to go after next [stage 1], etc).  Below is a brief listing of each stage and its associated tasks.

Stage 1: Prerequisites

• Identifying the targets (program interfaces to fuzz)
• Prioritizing your efforts (test planning)
• Setting Bug Bar

Stage 2: Creation of fuzzed data (malformed data)

• Will we be format-aware (e.g. most files follow a format)? Context-aware (e.g. order and/or timing of data may be important)?
• Will we use existing data (mutation) or generate it from scratch (generation)?
• Will the malformations we apply be based on type? Use interesting patterns? Over how many bits/bytes?
• Will we apply malformations with or without restriction? Are we going to be deterministic or random or both? How many times in a single iteration do we apply any given malformation?

Stage 3: Delivery of fuzzed data to the application under test

• Determining the best method to get the application under test to consume the fuzzed data (e.g. load path from cmd-line or GUI; API hooking; MITM proxies; DLL redirection; in-memory start-stop-rewind, etc)
• Implementing the appropriate delivery mechanism and conducting the test

Stage 4: Monitoring of application under test for signs of failure

• What should we look for?
• What do we do when we see it?

Stage 5: Triaging Results

• How can we classify and analyze issues found?

Stage 6: Identify root cause, fix bugs, rerun failures, analyze coverage data (rinse and repeat)

How we do file fuzzing

There are a number of approaches taken by product teams to meet the SDL file fuzzing requirements.  They often include the use of generation and mutation-based fuzzers as well as a combination of multiple internal and externally available fuzzing tools and/or frameworks. 

When fuzzing file parsers, we monitor for both handled and unhandled exceptions in the application under test.  Exceptions are events that typically represent error conditions encountered during the execution of an application.  They can be generated both by the hardware (initiated by the CPU) and/or software (initiated by the executing program or the OS).  To monitor for these exceptions, we created a mini-debugger using the Win32 Debugging APIs (For an example of how to integrate a debugger into your fuzz testing tool, check out Michael Howard and Steve Lipner's SDL Book at http://www.microsoft.com/MSPress/books/8753.asp).  The mini-debugger launches the application under test and monitors the parent and all subsequent child processes and associated threads.  When an exception occurred, the first version of this tool simply logged the file that caused the exception along with associated details such as the timestamp, exception code, exception address, stack trace and dump file.  More recent versions have included the ability to monitor for CPU and memory spikes as well as enabling full page heap settings on all processes launched from the mini-debugger.

As a general rule, all exceptions must be triaged (reviewed) by the tester to determine if a bug needs to be filed.  When fuzzing over a period of time however, we might generate hundreds of exceptions and it becomes a very labor-intensive process to sift through all of them.  What we needed was a way to ease the burden placed on the tester.

To that extent, the mini-debugger was extended to enable the automatic "bucketization" of logged exceptions to reduce the chance of having to look at duplicates during the triaging process.  This was accomplished by creating unique bucket ids calculated from the stack trace using both symbols and offset when the information is available.  The bucket id was used to name a folder that was created in the file system to refer to a unique application exception.  When an exception occurred, we calculated a hash (bucket id) of the stack trace and determined if we had already seen this exception.  If so, we logged the associated details in a sub-directory under the bucket id folder to which the exception belonged.  The sub-directory name was created from the name of the fuzzed file that caused the exception.  Thus, we were able to reduce the number of potential exceptions that a tester would have to look at during the triage process.  It is often the case that certain exceptions are noisy and/or expected so we also added the ability for the tester to dampen exceptions by exception code.  Dampening ensured that those exceptions were not logged (recorded) for triage during a fuzz run.  Nonetheless, despite our best efforts it is still possible for two different stack traces to have the same underlying root cause.

Even with all of this automated assistance, the tester might still have several hundred cases to triage.  In an effort to prioritize which cases should be triaged first, we introduced the notion of classifying exceptions.  Again, we extended the mini-debugger to perform classification on the exception code and relevant details.  In particular, we added an extra hierarchy over the automatically generated directory structure described above.  To do this we introduced the following categories of exceptions:

• Must Fix
• Further Investigation necessary
• Usually not exploitable

I know what you're thinking, but remember that this classification doesn't exclude a tester from the requirement of having to triage all exceptions.  The "Must Fix" category was composed of write access violations, read access violations on EIP, /GS and NX related access violations and read access violations where any one of the following was true*: 

• The access violation happens on a rep assembly instruction (on an Intel processor) where the count register (ecx) is large. 
• The access violation happens on a mov instruction where the result is used as the destination of a call in the instructions immediately after the mov.
• The access violation happens on a mov instruction where the result is later used in a rep instruction as the source (esi), destination (edi) or count (ecx).

*Fully automating the classification of these cases is complex and almost always requires an entire execution trace.   As such, teams are also provided with guidance to assist them during their analysis when our tool is unable to classify beyond "read and write access violations".

The "Further Investigation necessary" category was composed of read access violations that didn't meet the criteria above as well as other specific cases.  Finally, the "Usually not exploitable" category was composed of other exceptions such as divide-by-zero, C++ exceptions and the like.  Another thing to keep in mind is that the interpretation of "Usually not exploitable" is different for server-based components.  In other words, a divide-by-zero exception in a server product is probably more than just a robustness issue...it might be a denial of service!

Remember that regardless of this classification the tester is still required to triage all exceptions and file bugs accordingly.  I'll defer more details on the subject of exploitability of program failures to the upcoming annual security issue of MSDN Magazine in November.

To recap, we had a debugging plug-in (mini-debugger) that not only monitored for exceptions but also reduced the number of exceptions to triage after a fuzzing session was completed.  This also included monitoring for CPU and memory spikes as well as the use of page heap to capture heap corruptions that might not manifest themselves as an application crash (exception) during the fuzz session.  What could go wrong?  Enter MS07-017.  The software responsible for invoking the vulnerable code [to parse animated cursors] made use of an exception handler to recover from pretty much any exception that could be generated and continue operating as if nothing had occurred (Read more about it at http://blogs.msdn.com/sdl/archive/2007/04/26/lessons-learned-from-the-animated-cursor-security-bug.aspx).

The Animated Cursor bug caused us to revisit our mini-debugger.  Why?  Put simply, we hadn't introduced the "bucketization" and classification mechanisms for first-chance exceptions.  Naturally, this meant the tester was back to square one in terms of having no assistance on the labor-intensive triaging process. To deal with the "recover from anything" exception handling code we introduced the concept of classifying and bucketing "dangerous" first chance exceptions to help reduce the number of first chance cases the tester would need to triage.  This means we look for both write access violations and read access violations on EIP.  Additionally, we added support to continue after a first chance exception, allowing exception handlers to be called and continue and possibly proceed on to other more interesting crashes.

As you can see fuzz testing scales pretty well, but simplifying and scaling the triage process is not an easy task.  Even more challenging is the integration of technology into an effective lifecycle. We're constantly working with teams within Microsoft to further advance our tools, you can learn more by viewing http://research.microsoft.com/research/pubs/view.aspx?id=1333&type=Technical+Report and http://research.microsoft.com/Pex/. 

-Scott Lambert