CRM114 (program)

<h2 id="nomenclature">Nomenclature</h2>
The name comes from the <a href="/facts/CRM_114_(device)/nsFVd93e">CRM-114 Discriminator</a> in <a href="/facts/Stanley_Kubrick/y5cxcQzV">Stanley Kubrick</a>'s film <a href="/facts/Dr._Strangelove_or%3a_How_I_Learned_to_Stop_Worrying_and_Love_the_Bomb/QfYCyoPI">Dr. Strangelove</a> - a piece of radio equipment designed to filter out messages lacking a specific code-prefix.

<h2 id="operation">Operation</h2>
While others have done statistical <a href="/facts/Bayesian_spam_filtering/ytWrkz4a">Bayesian spam filtering</a> based upon the frequency of single word occurrences in email, CRM114 achieves a higher rate of spam recognition through creating hits based upon phrases up to five words in length. These phrases are used to form a <a href="/facts/Markov_Random_Field/DJazwaeP">Markov Random Field</a> representing the incoming texts. With this additional contextual recognition, it is one of the more accurate spam filters available. Initial testing in 2002 by author Bill Yerazunis<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> gave a 99.87% accuracy;<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> Holden <a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> and <a href="/facts/Text_Retrieval_Conference/XrFgbLQu">TREC 2005 and 2006</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> gave results of better than 99%, with significant variation depending on the particular corpus.
CRM114's <a href="/facts/Statistical_classification/jXXHRkXR">classifier</a> can also be switched to use Littlestone's <a href="/facts/Winnow_(algorithm)/Shdmb7AD">Winnow</a> algorithm, character-by-character <a href="/facts/Correlation/egkluAEm">correlation</a>, a variant on KNN (<a href="/facts/K-nearest_neighbor_algorithm/Bs1UaAmE">K-nearest neighbor algorithm</a>) classification called Hyperspace, a bit-entropic classifier that uses <a href="/facts/Entropy_encoding/44I0n8F8">entropy encoding</a> to determine similarity, a <a href="/facts/Support_vector_machine/XobxpdBG">SVM</a>, by mutual compressibility as calculated by a modified <a href="/facts/Lempel-Ziv/HGH09JM9">LZ77</a> algorithm, and other more experimental classifiers. The actual features matched are based on a generalization of <a href="/facts/N-gram/v4BT6rPP">skip-grams</a>.
The CRM114 algorithms are multi-lingual (compatible with <a href="/facts/UTF-8/xlaVHSyf">UTF-8</a> encodings) and null-safe. A voting set of CRM114 classifiers have been demonstrated to detect confidential versus non-confidential documents written in <a href="/facts/Japanese_language/EEv485a5">Japanese</a> at better than 99.9% detection rate and a 5.3% false alarm rate.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
CRM114 is a good example of <a href="/facts/Pattern_recognition/o1s38opj">pattern recognition</a> software, demonstrating how machine learning can be accomplished with a reasonably simple algorithm. The program's C source code is available under the <a href="/facts/GPL/S75KhLSX">GPL</a>.
At a deeper level, CRM114 is also a string pattern matching language, similar to <a href="/facts/Grep/PdGQeFfD">grep</a> or even <a href="/facts/Perl/fx31kjlT">Perl</a>; although it is <a href="/facts/Turing_complete/73goop44">Turing complete</a> it is highly tuned for matching text, and even a simple (recursive) definition of the factorial takes almost ten lines. Part of this is because the crm114 language syntax is not <a href="/facts/Positional/31DECoN4">positional</a>, but <a href="/facts/Declension/SWppkx4X">declensional</a>. As a programming language, it may be used for many other applications aside from detecting spam. CRM114 uses the <a href="/facts/TRE_(computing)/wu8cRhte">TRE</a> approximate-match <a href="/facts/Regex/KFL3veHX">regex</a> engine, so it is possible to write programs that do not depend on absolutely identical strings matching to function correctly.
CRM114 has been applied to <a href="/facts/Email_filtering/aKxq5uSf">email filtering</a> in the KMail client<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> and a number of other applications, including detection of bots on Twitter and Yahoo,<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> as well as the first-level filter in the US Dept of Transportation's vehicle defect detection system.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> It has also been used as a predictive method for classifying fault-prone software modules.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/String_matching/RCvwDRle">String matching</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://crm114.sourceforge.net">The CRM114 home page on SourceForge</a></li>
<li><a href="https://laurikari.net/tre">The TRE approximate regex matcher homepage</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Garretson, Cara (2007-03-19). "The antispam man". Network World. <a href="https://www.networkworld.com/article/2296297/the-antispam-man.html" target="_blank">https://www.networkworld.com/article/2296297/the-antispam-man.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">"CRM114 gets 99.87%". Paul Graham's website. 2002-10-16. <a href="http://www.paulgraham.com/wsy.html" target="_blank">http://www.paulgraham.com/wsy.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Spam Filtering II <a href="https://web.archive.org/web/20050307062526/http://sam.holden.id.au/writings/spam2/" target="_blank">https://web.archive.org/web/20050307062526/http://sam.holden.id.au/writings/spam2/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Spam Track Overview (2005) - TREC 2005 <a href="http://trec.nist.gov/pubs/trec14/papers/SPAM.OVERVIEW.pdf" target="_blank">http://trec.nist.gov/pubs/trec14/papers/SPAM.OVERVIEW.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Spam Track Overview (2006) - TREC 2005 <a href="http://trec.nist.gov/pubs/trec15/papers/SPAM06.OVERVIEW.pdf" target="_blank">http://trec.nist.gov/pubs/trec15/papers/SPAM06.OVERVIEW.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">"Archived copy" (PDF). media.blackhat.com. Archived from the original (PDF) on 2011-07-08.{{cite web}}: CS1 maint: archived copy as title (link) <a href="https://web.archive.org/web/20110708011918/https://media.blackhat.com/bh-us-10/whitepapers/Yerazunis/BlackHat-USA-2010-Yerazunis-Confidential-Mail-Filtering-wp.pdf" target="_blank">https://web.archive.org/web/20110708011918/https://media.blackhat.com/bh-us-10/whitepapers/Yerazunis/BlackHat-USA-2010-Yerazunis-Confidential-Mail-Filtering-wp.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">"Removing spam mail with CRM114 and KMail". Archived from the original on 2019-10-01. Retrieved 2019-10-01. <a href="http://www.nnc3.com/mags/LM10/Magazine/Archive/2007/77/074-077_kmail/article.html" target="_blank">http://www.nnc3.com/mags/LM10/Magazine/Archive/2007/77/074-077_kmail/article.html</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">"kmail.antispamrc at KDE/kdepim-addons". GitHub. 12 June 2022. <a href="https://github.com/KDE/kdepim-addons/blob/master//kmail/plugins/common/kmail.antispamrc#L223" target="_blank">https://github.com/KDE/kdepim-addons/blob/master//kmail/plugins/common/kmail.antispamrc#L223</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Chu, Zi; Gianvecchio, Steven; Wang, Haining; Jajodia, Sushil (November 2012). "Detecting Automation of Twitter Accounts: Are You a Human, Bot, or Cyborg?". IEEE Transactions on Dependable and Secure Computing. 9 (6): 811–824. doi:10.1109/TDSC.2012.75. ISSN 1545-5971. S2CID 351844. <a href="https://ieeexplore.ieee.org/document/6280553" target="_blank">https://ieeexplore.ieee.org/document/6280553</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">"Measurement and Classification of Humans and Bots in Internet Chat". Usenix. Retrieved 2023-01-16. <a href="https://www.usenix.org/legacy/events/sec08/tech/full_papers/gianvecchio/gianvecchio_html/index.html" target="_blank">https://www.usenix.org/legacy/events/sec08/tech/full_papers/gianvecchio/gianvecchio_html/index.html</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Scovel III, Calvin L. (2015-06-18). Inadequate Data and Analysis Undermine NHTSA's Efforts To Identify and Investigate Vehicle Safety Concerns (PDF) (Report). Office of Inspector General - U.S. Department of Transportation. <a href="https://www.oig.dot.gov/sites/default/files/NHTSA%20Safety-Related%20Vehicle%20Defects%20-%20Final%20Report%5E6-18-15.pdf" target="_blank">https://www.oig.dot.gov/sites/default/files/NHTSA%20Safety-Related%20Vehicle%20Defects%20-%20Final%20Report%5E6-18-15.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Mizuno, Osamu; Ikami, Shiro; Nakaichi, Shuya; Kikuno, Tohru (May 2007). "Spam Filter Based Approach for Finding Fault-Prone Software Modules". Fourth International Workshop on Mining Software Repositories (MSR'07:ICSE Workshops 2007). p. 4. doi:10.1109/MSR.2007.29. ISBN 978-0-7695-2950-9. S2CID 5867386. <a href="978-0-7695-2950-9" target="_blank">978-0-7695-2950-9</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
</ol>

CRM114 (program) open-in-new

CRM114 (program)