Parsing text for a Credit Card Number

A while back I wrote some code that parses text and looks for credit card numbers embedded in the text and then optionally masks all or some of the credit card in the text. This code is open source and available on GitHub: Credit Card Parsing

The main use case for this code was to remove credit card numbers that customers would email in to customer support when they were trying to buy something. The Payment Cards Industry (PCI) standards require the credit card data be stored under more secure conditions than most default standard storage configurations.

If customers' support tickets are being stored in a regular unencrypted database and they are sending you their credit card numbers then you are not PCI compliant. You have two choices. Make the support ticket database PCI compliant or remove the credit card numbers from the text that you're storing in this database.

The code in this library provides a mechanism to find and then optionally mask the credit card numbers in any block of text.

While I was developing this code I learned something interesting. 0.6% of all UUIDs/GUIDs have a valid credit card number in them. When I say valid I mean that it passes the Luhn Algorithm. I discovered this because our support emails had a lot of UUIDs that were part of URLs and other keys that the customers needed to communicate to us.

The first time I saw this false positive I thought that it was a one in a million chance. Not wanting to rely on that (bad) luck I used Monte Carlo Simulation to determine the probability of this happening and it came out at 0.6%. I had to adjust the credit card finding algorithm to ensure that what it thought was a credit card was not part of a UUID.

Development of this library was an unusual experience in that unit tests were immediately useful and protective. Each time a defect came back from production (i.e. a missed credit card or a false positive) I added that block of text* to a unit test and confirmed that it failed. I then fixed the code to ensure that the unit test passed and every time I did that it broke one of the other unit tests. My adherence to strictly unit test everything I wrote in this project ensured that it never had any regression bugs.

* If it was a missed credit card then that credit card would be replaced by a fake one before it was inserted into the unit test. I used Graham King's Credit Card Number Generator to create these fake credit cards.

Factorial Function in C#

 The Factorial Function is a classic interview question. It opens the doors to a discussion about stack overflow (if done recursively) and integer overflow (if the param is too large) as well as discussions around how to handle and catch errors.

Here is one way to do it using recursion:

static Int64 Factorial(int factor)
{
    if (factor > 1)
    {
        return factor * Factorial(--factor);
    }
    return 1;
}

Here is another way to do it using a loop: 

static Int64 Factorial(int factor)
{
    Int64 factorial = 1;
    for (int i = 1; i <= factor; i++)
    {
        factorial *= i;
    }
    return factorial;
}

Neither function does any sanity checks for input (e.g. >= 1) and assumes that we're looking for a factorial of 1 or greater.

There's a third and much better way to do factorials if you are going to use them in code that needs to be optimized. In fact I can't think of a reason why you wouldn't want to use the following method. If you are calculating an Int64 factorial then the maximum factor that you can calculate it for is 20. After that it will overflow the Int64 type. If you are calculating an Int32 factorial then the highest you can go is 12. 

static Int64[] factors64 = { 0, 1, 2, 6, 24, 120, 720, 5040, 40320,
362880, 3628800, 39916800, 479001600, 6227020800, 87178291200,
1307674368000, 20922789888000, 355687428096000, 6402373705728000,
121645100408832000, 2432902008176640000 };
 
static Int64 Factorial(int factor)
{
    return factors64[factor];
}

The tests that I ran showed the recursive factorial function to run 14 times slower than the array lookup and the loop to run 5 times slower.

Training a text classifier

When writing a text classification system you need to train it. Typically you have a corpus of good data that has been accurately pre-classified and this is what you throw at the system while it is learning the classification.

I came up with what I thought was a good analogy for an untrained text classifier: A genius amnesic. i.e. someone who initially knows nothing but learns lightening fast.

Text Classification References

I'm currently working on a text classification system. This is requiring a fair amount of research and background reading so I'm going to create a list of references that I'm using:

A Plan for Spam by Paul Graham

Better Bayesian Filtering by Paul Graham

Bayesian Filtering: Beyond Binary Classification [PDF] by Ben Kamens

Ending Spam: Bayesian Content Filtering and the Art of Statistical Language Classification by Jonathan Zdziarski

CRM114 Discriminator by Bill Yerazunis

A free online Bayesian Classification service that I recently found and tried is called uClassify. I found that it was remarkably accurate and contacted the owner and exchanged some emails with him. Unfortunately he uses a proprietary data store that he bundles as part of the commercial package that he sells which makes his product unscalable and impossible to fail-over. Hopefully one day he'll move the datastore so something like SQL Server to make this product more usable by more people.

 

Are there enough credit card numbers?

I was wondering if the 16 digits that most credit cards have (VISA and Mastercard et al) if you don't include American Express' 13 digit cards were enough for the world or if we'd run out of digits at some point.

If I've done my calculations correctly and based on my assumption that there are 7 billion people in the world then there are enough numbers for each person on earth to have just under 1.5 million credit cards.

I then pulled out my wallet and counted that I have 16 credit card sized items in there (some of which are credit cards) and held together they are about 1cm thick. So my next calculation was to see how fat my wallet would have to be to hold 1.5 million credit cards: 937.5 meters wide, that's almost a Km.

Casting Out Nines

I'm working on a project at the moment that involves the verification of credit card numbers. This has led to running checksums on the numbers to validate them including Luhn's algorithm.

Simply stated, Luhn's algorithm doubles every second digit (starting from the right) and then adds together all of those digits which it then mods against 10 to check for success. So if you had the sequence 2568 it would be transformed into 4-5-12-8. You would then add each digit together, the 12 would become 3 (1+2) and not be a 12. So your total is 4+5+1+2+8 = 20. Mod this against ten: 20 % 10 = 0 and if 0 then it passed the test.

In code, when computing the algorithm, you may end up with a 2-digit number after doubling it. Although you could convert it to a string and then convert each digit back to a number to add them together it's easier to subtract 9 from the doubled number which will give you the same result. 12 - 9 = 3 as does 1 + 2 = 3. This, I have just learned is called "Casting Out Nines." Cool term, I like it.

Here is the C# code that I came up with:

                int total = 0;
                bool even = false;
                for (int i = digits.Length - 1; i >= 0; i--)
                {
                    int current = digits[i];
                    if (even)
                    {
                        current *= 2;
                        if (current > 9)
                        {
                            current -= 9; // cast out nines
                        }
                    }
                    total += current;
                    even = !even;
                }