Proud of My Patch Panel

Today was my last day of work at my current company, and I paid a visit to the company’s offices to return company property and cleanup my drawer.

On my way out, I had a last glance at the patch panel of the office – it took me a few days in February 2010 to set it up, and I have to say I’m very proud of it. All the short cables are hand-made with precise lengths in order to make the panel look tidy, and important cables are labeled for quick diagnostics (“wireless”, “ADSL”, etc.).

I couldn’t bear the idea of the panel entering oblivion, and thus I shot a photo. Here it is, so that is won’t be lost forever in the archives of my memory…

The patch panel I've built and of which I'm very proud.

Chris Eng: How to Become an Information Security Thought Leader

Radi brought to my attention this post from Veracode’s Chris Eng on How to Become an Information Security Thought Leader.

This video reminds me of so many thought leaders I’ve met. If only I could get them to watch it now

A Dimensional Model for Vulnerability Management

For the past few months I’ve been working on an interesting problem for a large Dutch financial institution. The driver is a situation quite common in the risk management world: the security office of the institution is trying to centralize the reporting of all risk-related information, and among other things, vulnerability management data plays a central role. Information from vulnerability scanners needs to be correlated with information from network management and asset management in order to aggregate vulnerabilities up the IT architecture of the institution. A good design for the solution presents some unique challenges, and since I could not find too much help in the BI literature on the Internet, I thought I’d publish some of the results hoping to be of help to anyone else encountering the same design issues I’ve been fighting with for a while.

A simplified view of the data model for vulnerability management looks as follows:

• A vulnerability scanner reports the observation of a certain vulnerability class (e.g. of a certain Microsoft security bulletin) on a certain IP address;
• An IP address is hosted in a certain country and belongs to a certain host which, in turn, runs a number of IT assets (i.e. applications);
• An IT asset has an asset rating and belongs to a certain IT service.

After correlating the data, the institution would like to be able to answer questions such as:

• How many vulnerabilities do we have this month for each hosting country?
• How many vulnerabilities affect applications with this particular rating?
• What’s the trend of vulnerabilities for each IT service for the past 12 months?
• Which applications are affected by vulnerabilities that have been unpatched for this amount of time?
• How many vulnerabilities underwent this particular state change during the past N weeks?

The solution we are currently evaluating consists of two main components. A data warehouse provides the historical repository of the data, which is periodically updated with snapshots built by correlating the various sources of information. On top of this repository, various OLAP cubes provide an analytical interface to the warehouse, allowing security officers to answer questions by simply browsing the cubes with a pivot table.

The first cube I’ve been dealing with is the cube for the vulnerability management “universe” (in SAP terms), and it immediately proved to be a true design challenge for a number of reasons.

First of all, the dimensional model for this cube does not consist of a single fact, but rather, it encompasses a number of facts each providing its own measure(s) and each related to all of the dimensions in some way. As an example, we want measures such as number (count) of vulnerabilities, number (count) of applications, and number (count) of vulnerability state transitions, and each of these measures should be related, for example, to the Vulnerability Severity dimension, so that we can “plot” any of these measures against the various severities. It should be obvious that all of these measures cannot live in the same fact table, and thus the solution needs a dimensional model that deviates from the typical star/ snowflake model.

Second, many of the dimensions in this model are related to each other through a many-to-many relationship; consider, for example, the relationship between a host and an application, in which a host can run multiple applications and a single application can run on multiple hosts. Many-to-many relationships are usually extremely difficult to deal with in an OLAP cube – just think of the issue of counting the same thing twice through two cascaded many-to-many relationships – but the stack I’m currently considering (Microsoft BI with SQL Server Analysis Services 2005) elegantly supports many-to-many relationships through the use of “intermediate measures” (see Marco Russo’s excellent The many-to-many revolution whitepaper).

Finally, many of the relationships between the dimensions are dynamic, and for some of these the business would like to be able to report things as they were at the time the snapshots were taken. As an example, the same application can be run by different hosts each month, and thus the vulnerabilities affecting the application vary over time. In these situations, questions like “which vulnerabilities affect this application?” do not have much sense, as they should be better put as “which vulnerabilities affect this application at this point in time?”.

After a lot of thinking and endless discussions with the business, I finally homed in on an elegant dimensional model for vulnerability management, which I decided to model using the Dimensional Fact Model (DFM) approach (described in Rizzi’s paper).

Complete Fact Schema

The DFM for the vulnerability management “universe” is as follows:

In the model above I am using some terms in a way that differs from most “standard” security literature; in order to avoid misunderstandings, here are some clarifications on the terms in my ontology:

• Vulnerability: the occurrence, or instance, of a Vulnerability Class on a specific IT device, such as a host. For example, the presence of MS10-070 on host jupiter24.acme.eu.
• Vulnerability Class: a software weakness that exists regardless of its occurrence. For example, MS10-070. It goes without saying that a Vulnerability Class is related to a number of CVE ID’s.
• Vulnerability Observation: the observation of a Vulnerability at a specific point in time. For example, the detection of MS10-070 on host jupiter24.acme.eu which took place during the scan of January 3, 2010.
• IT Asset: an application or a set of applications behaving as a larger atomic system.

Some considerations on the model follow.

• Some of the facts in the model exist purely for the need of creating many-to-many relationships among dimensions (as explained in Russo’s whitepaper). This is true, for example, for the CVEID Observation fact, which models the many-to-many relationship between the Vulnerability Class dimension and the CVEID dimension, and for the Host Snapshot fact, which models the many-to-many relationship between the Host dimension and the IT Asset dimension. In these cases, I decided to attach a useful measure anyway, such as the total count of (distinct) hosts, so to be able to answer questions such as “How many hosts are used by this IT service? ” without incurring double-counting issues.
• The two date dimensions in the model – Scan Date and Snapshot Date – model two completely separate concepts. Scan Date contains dates of vulnerability scans, while Snapshot Date contains the date of the ETL snapshot. Speaking of which, we only need a single Snapshot Date dimension because the model is fully connected, and thus we can relate the Snapshot Date dimension with every fact – and consequently with all the other dimensions. I’ve arbitrarily attached the Snapshot Date dimension to the IT Asset Snapshot fact.

Dynamic Relations

My model handles dynamic relations in two distinct ways.

Dimension-dimension Relations
The relationships between separate dimensions, which are modeled with the use of “intermediate” facts, are treated with the “historical truth” approach, that is, they reflect the relationships that were in effect at the time of the snapshot. As an example, if in January host H1 ran asset A1 and in February the same host ran instead asset A2, then the host’s vulnerabilities in January would be aggregated to asset A1 and the host’s vulnerabilities in February would be aggregated to asset A2. In order to achieve this, there’s a trick that is key to the correct modeling of time in my model, and thus it deserves some more explanations.

Let’s expand on the previous example and assume that the following relations were in effect in January and in February:

• January: IP Address IP1 suffers from vulnerability V1 and belongs to host H1 which runs asset A1.
• February: IP Address IP1 suffers from vulnerability V2 and belongs to host H1 which runs asset A2.

Now, let’s say that in order to save on storage space, we want to employ a Kimball type-2 approach for our slowly-changing dimensions (SCD’s) and relationships. In other words, we do a sort of “compression” and re-use records for those dimensions and facts that haven’t changed since the last snapshot. Given that we expect only a small number of things to change from month to month, using type-2 SCD’s would allow us to save a lot of space. In this case, we would have a single dimension record for IP1 in both January and February, a single fact record for the IP Address Snapshot fact (the relationship between IP addresses and hosts, which didn’t change between January and February), a single dimension record for H1 in both January and February, and two different records for each of the remaining dimensions and facts, one record for January and one record for February. The situation would look as follows:

At first glance everything seems fine; we are loading lots of data each month, but in reality we only need to store the “deltas” for things that change; we don’t need to duplicate records for IP1, H1, and their relationship, since these haven’t changed at all. However, there is one huge problem with this approach. Let’s say you want to see the vulnerabilities affecting each asset in February. You would select the February value from the Snapshot Date dimension, and then the OLAP engine would have to join its way from the Snapshot Date dimension down to the Vulnerability dimension. The first step works fine – through the February-specific record of the Snapshot Date <—> IT Asset relationship (IT Asset Snapshot fact), the engine reaches the A2 record; cool. Now, from the February-specific record of the IT Asset <—> Host relationship (Host Snapshot fact), the engine reaches the month-agnostic H1 record. Not cool! H1 is not month-specific and so the engine has now no way of “propagating” the month-specific-ness from A2 to the IP addresses; in fact, from now on H1 is linked to IP1 which appears to be linked to both V1 and V2, as the OLAP engine does not know that it has to use the original choice of the month for the Snapshot Date dimension in its Vulnerability <—> IP Address table join. We could solve this by attaching another Snapshot Date dimension to the Vulnerability <—> IP Address relationship (i.e. to the Vulnerability Snapshot fact), but that would make the query cumbersome: you’d have to select two date dimensions and then select the same value for both dimensions.

Seen from another angle, the issue is that the OLAP engine (at least SSAS’s) “walks” the graph of dimension-fact relationships by means of table joins with simple field equality predicates (i.e. “table1.fk = table2.pk”); in order to “propagate” the month choice, you would have to tell it to consider also the month in the join predicate, which unfortunately you can’t do. The simplest way to ensure separation of time is thus to have completely separate graphs for each snapshot, even for arcs and nodes that do not change; this way, “anchoring” a date with the single Snapshot Date dimension means selecting a single instance of the graph – the one that models the universe at that date – and so that “anchor” can be propagated to the whole graph by means of its topology only. In other words, this is equivalent to including the Snapshot Date dimension value in each primary key involved in the graph joins, with the effect that each record in each fact table and each record in each dimension table becomes unique per-snapshot. To achieve this, during each ETL the records in the dimension tables are completely re-created from scratch, and fact records (i.e. relations) are completely re-created from scratch using the surrogate keys of the new dimension records. The same situation of before would then look like this:

There is of course some degree of waste of space – after all, H1 hasn’t really changed, yet we duplicate its records in January and in February. This waste of space, however, can be significantly contained by ensuring that the actual metadata associated with H1 (i.e. the values of its hierarchies’ attributes) live in a separate “dimension metadata” table, treated as a type-2 SCD; the Host dimension record contains the foreign key to this metadata table, rather than the metadata itself, and thus we reduce the size of the dimension records to two fields – the dimension’s surrogate key and the dimension’s metadata table key.

You could argue that there is still room for space optimization here. In our previous example, if IP1 suffered from V1 in both January and February, then we could have stored the Vulnerability <—> IP Address <—> Host chain only once, and “fork” only at the Host <—> IT Asset arc, as shown in the following diagram.

In more formal terms, if you pivot the model’s graph to look like a tree rooted at the Snapshot Date dimension node, then you could say that we can treat as a type-2 SCD each complete sub-tree that hasn’t changed between ETL periods. The problem, however, is that doing this form of “constant sub-tree detection” could be quite complex to perform in an ETL, and so I would personally choose to duplicate the entire graph (tree) and waste some space rather than risking incorrect reporting due to bugs in the ETL process.

Attribute-attribute Relations
Differently than dimension-dimension relationships, the relationships between the attributes in the hierarchies within a dimension are treated as “today for yesterday”, that is, the latest situation replaces the relationships in the past (effectively a type-1 SCD). As an example, if in January the IT service S1 belonged to Switzerland and in February the same IT service belongs to China, then after February the S1 vulnerabilities in January would be aggregated to China. The reason for this behavior is that these types of changes are assumed to be “improvements” in our knowledge of the universe, and thus corrections in our knowledge are assumed to be retroactive. At the same time, treating attributes and their relations as type-1 SCD’s allows us to save storage space, which is especially good in light of the fact that, as we have seen, we need to completely duplicate dimension and fact records at each snapshot. It’s worthy to note that the underlying data warehouse still stores the information as type-2 SCD’s, in order to support ad-hoc forensic investigations; it’s only the OLAP cube that models these are type-1 SCD’s.

Published with full permission of my client.

OWASP and Input Validation

As a follow-up to my previous post, here’s another example of OWASP’s “authoritative” prescriptive guidance that gives developers advice that is, in my humble opinion, dangerously wrong, and which contributes in building that sort of “parrot security expertise” – i.e. expertise that is based on repeating nonsensical mantras – which you see unfortunately way too often in the software security field.

From the Injection Prevention Cheat Sheet at owasp.org:

Injection Prevention Rules

Rule #1 (Perform proper input validation):
Perform proper input validation. Positive or “whitelist” input validation with appropriate canonicalization is also recommended, but is not a complete defense as many applications require special characters in their input.

Rule #2 (Use a safe API):
The preferred option is to use a safe API which avoids the use of the interpreter entirely or provides a parameterized interface. Be careful of APIs, such as stored procedures, that are parameterized, but can still introduce injection under the hood.

Rule #3 (Contextually escape user data):
If a parameterized API is not available, you should carefully escape special characters using the specific escape syntax for that interpreter.

Notice how input validation is listed as the first rule here. Basically, OWASP is saying that “if you can, you should put a patch in front of it“, rather than actually fix the bug itself. So much for good engineering, this is security done by sprinkling some dust to patch holes here and here.

Fixing the bug itself – i.e. escaping the data that the developer forgot to escape to start with – is only listed as the third rule, to be used in case the other two fail.

If I were a developer seeking advice on how to write secure software, what would I take from this? I would probably remain firm in my opinion that writing secure software is just a matter of using security features here and there, such as the validators offered by my programming framework, rather than being a matter of creating solid code that is developed correctly in the first place. So, I can continue writing my sloppy code, and then add validators here and there to make my software robust.

Now, some of the OWASP people counter-argument that “you live in a fairy-tale world; in the real world, there are sloppy developers and you need an approach that secures their code too“. Really? This is exactly the same as saying “you live in a fairy-tale world; in the real world, there are developers who write a sort function with cubic complexity and you need an approach that speeds up their code too“. So, the reasoning goes, OWASP is saying that instead of studying algorithm theories and requiring that our developers read Knuth at least once in their lives, we should all write sorting algorithms that run in cubic time, and “if we can”, just run this sloppy code on beefy boxes, and we’ll all be happy with that. I’m sure that on a 360-teraflops box my cubic sort will be as fast as sloppy code is secure with a regex validator in front of it.

Input Validation & Injection Vulnerabilities

Nothing pisses me off more quickly and surely than a security consultant boasting that “you can solve your [insert favorite injection vulnerability here] issue with proper input validation”.

OWASP does this all the time, with preposterous sentences like the following, taken from this page:

Input validation is absolutely critical to application security, and most application risks involve tainted input at some level.

This is what happens when you take a couple of graduates out of school and thrust them into the client’s dev team as the “security consultants”. And, probably, nothing has contributed more to damage the reputation of security consultants as this claim has been doing for the past tens of years. Advocating input validation as the first line of defense against injection vulnerabilities is like Microsoft forbidding users from typing “for”, “if”, or “while” in Office Word in fear that a victim could execute arbitrary code by feeding a Word document to a compiler. It’s like preventing race conditions by carefully avoiding to spawn any threads, or preventing buffer overflows by ensuring that all buffers are “kept small”.

Injection vulnerabilities – i.e. those nifty vulnerabilities like cross-site scripting (XSS), SQL injection, XPath injection, OS command injection, and so on – are caused by one simple thing: the dumbness of a developer not seeing that he’s using one channel (i.e. an HTML page, or a SQL query) to convey two types of content (i.e. rendering directives and text content, or SQL statements and literal parameters). A 5-year old kid will tell you that if you want to shove two separate messages into the same channel, you’ll need to use some type of encoding to keep them separate. A real developer knows this and makes sure that the two messages are kept separate by encoding the one that’s supposed to be encoded. A dumb (or lazy) developer doesn’t and ends up mixing things up. When the lazy developer concatenates strings to build HTML and forgets to HTML-encode the text in order to avoid it being parsed as rendering directives, what’s the bug? Is it lack of encoding, as plain software engineering thinking would suggest, or is it “bad, nasty, malicious input”, as most security consultants keep swearing? In other words, do injection vulnerabilities originate from lack of separation between messages in the same channel, or do they originate from the evil nature of the messages being mixed up? Well, if it were the latter, then the various RFC’s governing the structure of HTML, SQL, and the like would not have spent time telling you how to encode things. They would have said “Oh, by the way: you can’t have an HTML page that uses the ‘<’ or ‘>’ characters, we are sorry. HTML is not for math, buddy.”

Despite these obvious observations, many security consultants still advocate the use of input validation as the first line of defense against injection vulnerabilities. Input validation? Sure, show me. I have this forum in which people post arbitrary messages. Should I prohibit my users from posting math inequalities, which make use of ‘<’ and ‘>’? What about ‘&’? I should forbid that one as well, right? And what will happen when my users will try to edit their previous posts after I’ve implemented your input validation? Posts that were legitimate and innocuous yesterday all of a sudden become invalid and can’t be edited.

And what should I do with the “last_name” field of my form? I’m afraid of SQL injection, should I forbid the use of the single-quote character? Ooops, just got a call from support: we’ve just cut off all of our Irish customers – O’Brian, O’Bannon, and O’Sullivan, they can’t login anymore. How could anyone allow the Irish to have those dangerous, evil, malicious characters in their last names? Oh wait, is the single-quote character good now? I don’t get it, it was bad the day before yesterday and now instead you tell me it’s good. Do you have the slightest idea of what you’re talking about?

And finally, my application saves the user’s profile to the backend database. I’m not sure what happens next, the other department – or the other company – takes care of that. They might use my data to build HTML, sure, so let’s forbid ‘<’, ‘>’, and ‘&’. And since we don’t know whether they use AJAX, let’s be safe and forbid ‘{‘, ‘}’, and the double-quote character. You never know. Oh, they might also use this data to build SQL queries, of course, so let’s forbid the single-quote character. And since they often generate CSV log files, I’d say that ‘,’ should be illegal. And since their sub-system might also generate space-separated log files, I’m better safe than sorry – let me forbid the space character. That character is pure evil, I always suspected that.

What’s worse, the security consultant will not only tell you that you have to filter and validate your input. He will actually tell you how you have to do it: be careful, it’s all about black-listing versus white-listing. Black-listing is bad, as it’s likely that you forget some characters and end up with a security hole. Which would, of course, be caused by that single character that you forgot, not by the complete lack of output encoding throughout your code. The fact that you have been put in charge of writing a Web application because you googled “Perl” one day and learnt how to serve a Web page has absolutely nothing to do with the fact that you are riddled with injection vulnerabilities. It’s the character that you forgot to filter out, that’s the culprit.

So, it’s always better to use white-listing, because the worse that can happen is that all your users from Ireland, Italy, Spain, France, Germany, and any other country that uses characters other than those 26 you shoved in your white-list regular expression will be cut off from your Web app. Better safe than sorry, dude. Never mind that I lost a few million customers.

Oh, by the way, security consultant, look, WordPress.com allowed me to type ‘&’ in the title of my post. It must be vulnerable to cross-site scripting then.

Chip? No, Thanks

An awesome example of how banks and the payment industry try to screw customers.

In the Netherlands, the payment cards handed off by the banks usually have a magnetic strip and a smart card chip. However, stores here gladly accept the magnetic strip and I’ve never been requested to use the chip. I only had to use the chip in Italy, where angry clerks would say “no, turn the card around, can’t you see the chip?”. Apparently, the chip is going big everywhere else in Europe, and banks are marketing the EMV system – the technology behind the payment with the chip – as a safe way to prevent fraud.

They don’t tell you, however, that the EMV system has a serious design flaw which makes the magnetic strip a safer alternative. And they don’t tell you that if you get frauded, you lose the money.

My colleague Radi, in fact, just wrote a post about this paper that shows how a stolen chip card can be used in a successful transaction without knowing the PIN. Thew worst part is that by using this method, the bank thinks that the PIN was used during the transaction, and if the bank thinks you used the PIN, then, legally, you are responsible for the fraud.

The whole issue behind this flaw is that the PIN verification is left to the card, and the bank never sees the PIN. This is different from the magnetic strip method, in which the PIN is sent – encrypted – to the bank for verification.

This is why I just put a piece of plastic tape on my chip. The next time a clerk takes my card and inserts it face down in the chip reader, I will smile and say “No, thanks – the chip is broken”.

Touchdown: HiSam Will Be Going Live Soon!

A few days ago I finished the exhausting re-labeling effort that I had talked about previously, and I started running tests to see where I finally stand against my stated goal.

At first the results were a bit discouraging. With the final set of labeled documents – 2,000 sentences added to the previous 2,500 sentences – the overall F score went down a bit. I was kind of expecting this though, as the more training data from heterogeneous domains you add to the mix, the more variance you have in the thing being learned, resulting in both more potential for errors and more difficulty in learning. This fact is nicely explained by the following excerpt from this paper on static code analysis tools:

The result of summing many independent random variables? A Gaussian distribution, most of it not on the points you saw and adapted to in the lab. Furthermore, Gaussian distributions have tails. As the number of samples grows, so, too, does the absolute number of points several standard deviations from the mean. The unusual starts to occur with increasing frequency.

The final overall F score – 0.864 at 90% – is still far away from my goal of 0.900 at 60%, and the entity-specific F scores (e.g. 0.900 for GeoLocation entities and 0.915 for Person entities) are far from the F scores boasted by research projects in entity extraction – which are all around 0.93.

So, this very morning I decided to do a real-world test: I took a few articles from CNN, fed these to my HMM, and observed the results. I was astonished!!!!!! The little guy did extremely well with these pieces of text it had never seen before. Here are a few examples – colors correspond to entity types and numbers indicate the probabilities of the extracted entities:

Example 1:

Greene: ” This is about the limitless capacity of the human heart. ” Bob Greene says a small town in Ohio is one of the most inspiring places in the United States.

• Greene (Person: 5.99677679935634E-05)
• Bob Greene (Person: 1.25848620925595E-07)
• Ohio (GeoLocation: 0.001397929451232)
• United States (GeoLocation: 0.00286421623850843)

Example 2:

Until, on July 20, 1969, Neil Armstrong, of Wapakoneta, walked on the moon.

• July 20 , 1969 (Time: 0.000150556184495453)
• Neil Armstrong (Person: 1.33506658714912E-07)
• Wapakoneta (GeoLocation: 6.91960283284816E-07)
• moon (AstronomicalPlace: 0.351350422734393)

Example 3:

A soldier mans a weapon at the rear of a U.S. Army helicopter over Afghanistan in May.

• U.S. Army (Organization: 3.40883387762237E-06)
• Afghanistan (GeoLocation: 0.000349482362808)
• May (Time: 0.00299625468107284)

Example 4:

Senate Judiciary Committee considers Sotomayor nomination on Tuesday.

• Senate Judiciary Committee (Organization: 3.66993148614553E-10)
• Sotomayor (Person: 5.60905081933395E-07)
• Tuesday (Time: 0.0389513108539469)

So, why the poor F score and the good results? Well, I think I’ve found the explanation. As I said here, when I calculate the performance of my HMMs I’m being Nazi with myself: all the papers I’ve read, in fact, count the number of tokens correctly tagged by their systems, while I count the number of correct tags. This means that when my HMM extracts “Ohio” from “I’m going to Northern Ohio”, I count that as zero recall – the expected tag is “Northern Ohio” and my guy hasn’t found it. On the other hand, research papers would count that as one token out of two, which yields a 0.5 recall.

With this in mind, the results are so good that I’ve decided to set in motion the “release” machine. It took me a couple of years but the first piece of HiSam will finally be live soon!!!!

These are the last TODO items before I start working on the commercial offering:

1. Add an option to calculate the F score using the research papers’ method, and compare this score to their score;
2. Label a few more documents in order to reach better stability and see whether the learning curve shifts up;
3. Compress the XML serialization of the model – the current XML takes up 800Mb of disk space and takes forever to load…

Canary Hell

I’m finally back from my London stay, and I’m finding the time to answer a question that many asked me with incredulity: how it comes it took you 1 and ½ hours to commute between Chelsea and Canary Wharf?!?!?

Guess what, this is the Canary Wharf tube station at the time I used to get there:

(photo by Radi)

IMHO, getting from one point to the other among this crowd in 1 and ½ hours seems an achievement to me…but still, I had to endure skeptic eyes over and over while I was complaining about the commute.

Improving the Model

For the past couple of months I’ve paused further development of the model itself (the “MultiEntity” model) in order to focus on a last round of re-labeling of the training data with three goals:

1. Label new types of entities (monetary values and time expressions) together with the three “classic” ones (person names, geographical places, and organizations);
2. Be more strict with my labeling and make sure to adhere to a set of guidelines that I’ve implemented with the goal of ensuring consistency of the training data;
3. Enable a new mechanism that takes advantage of the inner structure of certain entity names – which is proving to be the key difference in reaching very good performance and on which I’m not yet ready to publicly elaborate.

At the same time I have also re-tokenized the training text being labeled in order to take advantage of some improvements I had done in the past years in the tokenization module.

On December 22 I reached a milestone – 60% of the “old” training data re-tokenized and re-labeled, about 2,900 sentences – and I decided it was time to pause the re-labeling effort and see whether I was going towards the right direction.

The first performance numbers were encouraging, but not as better than those before the re-labeling effort as I hoped they’d be. In order to investigate the reason for the modest improvement, I’ve employed a very useful technique that I had used earlier with a similar goal, a technique that I call “self-testing” and which I think I heard about in the machine learning literature.

Ideally, when you test your trained model on the same data that you have used to train it, you should see no errors in the model’s predictions. It’s kinda like asking a student to repeat the pages of the schoolbook she has just studied. In reality, however, the model does make some errors, exactly like the human student does , and these errors can be attributed to one of two different causes:

1. Noisy Training: the training data is not consistent because of some mistakes that took place during the manual labeling, and the learning algorithm is confused by these mistakes. Think of a student being told on Monday that 2 + 2 is 4, and then on Tuesday that 2 + 2 is 5. In my case, it could be that “China” has been tagged as a GeoLocation in one training sentence and erroneously as a Person – or not tagged at all – in another sentence.
2. Limited Learning Capability: the model is unable to learn from the training data due to limitations inherent to its design. Think of a primary school student being told that she can integrate Schrödinger’s wave function to get the probability that a particle is at X, Y, Z and has moment m. In my case, “Capitol Hill” might have been labeled as a GeoLocation in “The teacher lives on Capitol Hill” and as an Organization in “Last week Capitol Hill passed the bill”, and the model might not be considering enough context (prefix and suffix) in order to be able to discern these two different meanings of “Capitol Hill”.

When I originally ran the self-test before Christmas – on the 2,900 sentences re-labeled so far – the model came back with hundreds of errors. I spent most of the holidays’ development time analyzing the errors and improving the model, with results that were encouraging by the day. This chart shows the daily changes in the average F score of the model when trained with 90% of the re-labeled data and tested on the remaining 10%:

The improvements shown in the graph are due to a combination of interventions.

First of all, the self-test pointed me to a number of labeling errors, which I promptly fixed. When the training data became error-free, I attacked the problem of dealing with tokens containing numbers (e.g. “340”), which I never had reason to worry about before, ending up with the huge improvement in the performance of the newly-introduced Currency entity.

Finally, my “secret” recipe kicked-in. Leveraging the flexible configurability of the model and fine-tuning it based on analyses of the errors allowed me to obtain the improvements shown with the Person, GeoLocation, and Organization entities. This novel technique I’m using exploits the internal structure of certain entities and takes advantage of the fact that these different entities all “live” in the same model. As an example, consider Organization entities like “Bank of Japan” and “Bank of England”. If the model is capable of understanding that the third token of these entities is always a GeoLocation, then it will be more inclined to flag “Bank of Italy” as an Organization when it sees it for the first time, provided that its vocabulary of GeoLocation literals is comprehensive enough to flag Italy as a GeoLocation. Similarly, the model has been trained to discern, for example, between one-word GeoLocation entities (like “China” and “Italy”) and two-word GeoLocation entities (like “South Korea” and “Northern Ireland”). By being able to make this distinction, the model will be less inclined to flag “Northern” alone as a GeoLocation – which is exactly what used to happen before my intervention. As one would expect, the number of states has exploded from about 300 to 1,280 after all the fine-tuning, but thanks to Freitag’s and McCallum’s interpolation of emission probabilities, I haven’t experienced any penalty from the fragmentation of states.

All of this contributed to an overall improvement of the F score from 0.795 to 0.869, with Organization entities alone improving to 0.824, well above the best score of 0.755 that I was capable of obtaining last October before the re-labeling effort and before the finalization of my “secret recipe”. Moreover, the current performance of Person entities is exactly as it was when the old model was trained with 2,000 more training sentences.

At this moment all I need to do is complete the re-labeling – about 2,000 sentences left – and hope that the new training data raises the F towards my goal.

Google, Synonyms, and Coca-Cola

A few days ago I was googling for “security CCE-263″ (I was looking for MITRE stuff) and I got back results that showed “Coca-Cola” in bold, as if I had searched for that term. Weird, I thought. I soon realized that “security” had nothing to do with it, and so I searched for sugar CCE-foo, getting results like this:

Free coca cola sugar packet Download

Free coca cola sugar packet Download at WareSeeker.com – Colasoft Packet Player … foo packet decoder ac3 is a lightweight and useful add-on for foobar2000 …

Why have i stopped drinking coca cola? « Foo's blog

11 Oct 2009 … Firstly it was never good for the health, it has a ton of sugar and caffeine. … Companies like Coca cola do not operate democratically, …

Jones Soda – Wikipedia, the free encyclopedia

By April 2007, all of the company's products switched to cane sugar, ….. The Seahawks previously sold soft drinks from The Coca-Cola Company; …

After a few seconds I realized that the actual name of the Coca-Cola company is “Coca-Cola Entreprises”, or “CCE” for short. So it appears that Google is seeing “CCE” in my query and searching for “CCE” and “Coca-Cola” at the same time. Now, my question is: is Google doing this for *everything*, or is it only doing it for named entities (i.e. persons, organizations, geographic locations, etc.)? Moreover, is it doing this with acronyms only or also with generic highly-correlated words?

To answer the first question, I searched for other organization acronyms that I thought would be pretty common, checking the results to see if I could see the full name of the entity returned as a keyword, i.e. in bold. I tried with “SEC”, “FBI”, “CIA”, and “EPA”, and in no case I got back the full name of the entity as a keyword. Check it out – compare “EPA offices” with “CCE offices” and see how “Coca-Cola” is the only full company name that is returned as a keyword.

To answer the last question, I tried to search for “event viewer microsoft” in the hope that being “microsoft” and “windows” probably highly correlated, Google would return entries containing “windows” in lieu of “microsoft”; this is not the case though (as one would expect!), as the search does not return “windows” keywords. Moreover, searching for “msft redmond” does not return “microsoft” keywords, suggesting that the link between “Coca-Cola” and “CCE” is not simply based on high correlation of the occurrences of the two words, nor on acronyms.

So, I’m now left with one possibility only: something’s going on between Google and Coca-Cola