Tuesday, June 22, 2010

Brasileiro desenvolve novo algoritmo de pattern-matching super eficiente

Apesar da falta de investimento em pesquisa e desenvolvimento em tecnologias relacionadas à Segurança da Informação, existem alguns brasileiros que se destacam inovando em uma área praticamente dominada por chineses, israelenses, indianos e americanos.

Um destes brazucas é Breno Silva, que criou um algoritmo de pattern-matching que está sendo super bem recebido pela comunidade internacional.

Breno estará apresentando seu algoritimo na apresentação "Protecting smart-grid with BRENO-SILVA single pattern match algorithm for small patterns" evento IEEE Machine Learning and Cybernetics que aconterá na China em Julho.

Seguem algumas informações passadas pelo Breno sobre o assunto em uma rápida entrevista (as perguntas foram removidas para uma maior clareza e coesão do texto):
Vou estar publicando meu algoritmo single pattern match. O algoritmo foi criado pensando no projeto Suricata e ainda está no meu TODO colocá-lo funcionando dentro desse IPS.
O algoritmo tem se mostrado o mais eficiente atualmente para busca de patterns pequenas em super-alfabetos. O que é um problema ainda não muito bem resolvido para IDS/IPS e outras aplicações que fazem busca de patterns em rede IP. O algoritmo tem uma melhora na complexidade em pior e médio caso usando técnicas de skip e hashing para fazer a busca de patterns.
Basicamente o algoritmo foi projetado para ser eficiente na busca de pequenas patterns em super-alfabetos. Pattern pequenas sempre foram performance killers nesse tipo de aplicação e ainda se utilizavam algoritmos mais classicos para resolver esse problema.
Nenhum dos algoritmos comumente utilizados (Knuth-Morris-Pratt, Shift-And, Shift-Or, Boyer-Moore, Boyer-Moore-H) conseguiram ser mais rápidos. Também testei recentemente com um novo algoritmo publicado esse ano por um grupo de pesquisadores da Finlândia (SBNDMq) e um novo algoritmo que ainda será lançado pelo francês Thierry Lecroq (EBOM). Nenhum deles foi mais eficiente. O algoritmo criado foi pelo menos 50% mais eficiente nesses casos dos que os comparados.
O algoritmo se torna mais eficiente com o aumento do alfabeto. Pode ser uma boa opção para ferramentas de forense de rede e até mesmo para análise de logs.
Outro uso do algoritmo será possível em alguns anos - quando redes smart-grid forem uma realidade - e que provavelmente terão que trafegar um volume muito grande de dados, talvez haja necessidade de trabalhar com algoritmos mais eficientes daqueles que temos hoje em dia.
Um artigo científico que explica o funcionamento do algoritmo bem como testes comparativos com outros algoritmos comumente utilizados para essas tarefas será publicado em julho desse ano na International Conference on Machine Learning and Cybernetics (ICMLC) - China e depois disponível via ieeexplore.
Ainda não apresentei esse trabalho publicamente no Brasil, mas algumas pessoas do meio acadêmico estão interessadas em levar aos alunos. Particularmente eu espero bastante ter o apoio de pesquisadores para trabalhar em uma "versão" multi-pattern matching do mesmo algoritmo.

7 comments:

  1. Dá-lhe Brasil!

    ReplyDelete
  2. Isso aí, Brenfa. Daqui a pouco Google lhe contrata como VP Sênior de Engenharia.

    ReplyDelete
  3. Iuhuuuu... Breno cabron!! hehehehe :)

    Pena que essas coisas são praticamente ignoradas no Brasil... Dão mais valor a:

    - tradutores de textos (em sua maioria, textos antigos), tipo coisas de 1990...

    - kaozedsource, nem preciso falar ne?

    - coisas antigas "reencorpadas"...

    - copias de tendencias falidas (mesmo com o advento da globalização, ainda copiamos propostas que um dia foram boas, mas hoje não se aplicam).

    Marketing é tudo né não?

    Mas tambem não posso falar muito, sou o primeiro a não ter tempo/não fazer questão de não ajudar em nada! hehehehe

    ReplyDelete
  4. Complementando...

    Pena que essas coisas são praticamente ignoradas no Brasil... Dão mais valor a:

    - Rebolation

    ass. Kin

    ReplyDelete
  5. Beleza Breno!!!

    Estou orgulhoso do trabalho que você tem feito e do reconhecimento obtido.

    Parabéns

    Alexandre Cezar

    ReplyDelete
  6. Você sabe se ele já postou esse algoritmo em algum lugar?

    ReplyDelete
  7. Sim Anônimo, no http://ieeexplore.ieee.org/

    Ele me disse que você pode procurá-lo para mais detalhes.

    Att,

    S.S.

    ReplyDelete

Labels

forense (50) resposta a incidentes (40) segurança em profundidade (27) vulnerabilidade (27) treinamento (22) cyberwar (18) conferência (16) forense de memória (15) hackers (15) malware (15) blogs (14) vazamento de informações (13) windows (13) ddos (12) china (11) criptografia (11) dns (11) exploit (11) google (11) microsoft (11) ferramenta (10) memoria (10) botnet (9) csirt (9) forense de disco (9) forense de rede (9) ftk (9) legislação (9) phishing (9) 0-day (8) NIST (8) accessdata (8) encase (8) evento (8) ferramentas (8) kaspersky (8) linux (8) negação de serviço (8) netwitness (8) sans (8) volatility (8) cert.br (7) correlacionamento (7) desafios (7) forense corporativa (7) internet explorer (7) livros (7) pageviews (7) pci (7) privacidade (7) twitter (7) usa (7) APURA (6) Guidance Software (6) espionagem industrial (6) governo (6) iccyber (6) metasploit (6) monitoração (6) skype (6) techbiz (6) 0day (5) CDCiber (5) blackhat (5) brasil (5) dlp (5) falha (5) fbi (5) ids (5) inteligencia (5) java (5) memoryze (5) modelagem de ameaças (5) métricas (5) nsa (5) patch (5) pdf (5) policia federal (5) python (5) registry (5) richard bejtlich (5) rsa (5) segurança (5) segurança de rede (5) siem (5) CyberCrime (4) Enscript (4) adobe reader (4) algoritmo (4) android (4) anti-forense (4) anti-virus (4) arcsight (4) auditoria (4) backdoor (4) backtrack (4) campus party (4) ccc (4) certificação digital (4) ciberespionagem (4) defacement (4) drive-by (4) estatísticas (4) exploit kit (4) firefox (4) fud (4) gsi (4) mandiant (4) md5 (4) online (4) pentest (4) programação (4) safe browsing (4) sandbox (4) slowloris (4) ssl (4) storm worm (4) stuxnet (4) trojan (4) wikileaks (4) windows7 (4) .gov (3) ameaça (3) blackberry (3) ceic (3) chrome (3) ciberguerra (3) cloud (3) conscientização (3) crackers (3) cymru (3) dan geer (3) defesa (3) dsic (3) engenharia social (3) enisa (3) evidence (3) fast flux (3) forense digital (3) hardware (3) htcia (3) https (3) imperva (3) intel (3) ips (3) live cd (3) logs (3) man in the middle (3) networkminer (3) perícia digital (3) processo (3) ransomware (3) registro (3) reportagem (3) revista (3) risco (3) secunia (3) shell (3) shodan (3) sox (3) sql injection (3) tools (3) truecrypt (3) verizon (3) virus (3) vista (3) voip (3) worm (3) .mil (2) BSIMM (2) Encase Enterprise (2) JDFSL (2) TPM (2) Virustotal (2) XSS (2) adobe flash (2) aduc (2) amazon (2) apache (2) apple (2) autenticação (2) bloqueador de escrita (2) breno silva (2) bruce schneier (2) bundestrojaner (2) cache poisoning (2) caine (2) carders (2) carnegie mellon (2) carolina dieckmann (2) carving (2) censura (2) cipav (2) cofee (2) coldboot (2) comodogate (2) conficker (2) consciência situacional (2) cooperação (2) core (2) cucko´s egg (2) cuda (2) cyberwarfare (2) database security (2) digital intelligence (2) direito digital (2) dnschanger (2) dpf (2) engenharia elétrica (2) engenharia reversa (2) etir (2) expressões regulares (2) f-response (2) finfisher (2) fingerprinting (2) firmware (2) flash (2) fraude (2) ftkimager (2) full disclosure (2) fuzzy (2) gsm (2) hacktivismo (2) hbgary (2) heap spray (2) iOS (2) immunity (2) impacto (2) insecure magazine (2) insiders (2) interceptação (2) iphone (2) irc (2) irã (2) jaquith (2) loic (2) mac (2) mastercard (2) mestrado (2) mobile (2) ms08-067 (2) openioc (2) openssl (2) otan (2) palantir (2) paypal (2) pcap (2) pdgmail (2) portugal (2) presidência (2) prisão (2) proxies (2) ptfinder (2) rbn (2) recompensa (2) recuperação (2) regripper (2) relatório (2) resumo (2) rio de janeiro (2) ross anderson (2) russia (2) securid (2) segurança por obscuridade (2) sift (2) snort (2) snowden (2) sony (2) sorteio (2) spam (2) spoofing (2) spyeye (2) sql (2) ssd (2) stealth (2) suricata (2) sysinternals (2) tecnologia (2) trend micro (2) unb (2) usb (2) virtualização (2) visa (2) vulnerability (2) waf (2) winen (2) wireless (2) wpa (2) wpa2 (2) xry (2) zeus (2) .edu (1) .pac (1) 3g (1) ABNT (1) AR-Drone (1) AppleGate (1) Asterisk (1) Audit Viewer (1) BIOS (1) CCDCOE (1) CEF (1) CERT (1) CSI Cyber (1) CarbonBlack (1) Craig Wright (1) DC3 (1) Diginotar (1) Dilma (1) DoD (1) Equation (1) FACE (1) FRED (1) Facebook (1) Fred Cohen (1) GPU (1) Gene Spafford (1) HP (1) ICOFCS (1) ICS (1) IDMEF (1) IJDCF (1) IJDE (1) IJOFCS (1) INFOSEG (1) IODEF (1) IPv6 (1) ISIS (1) ISO (1) MAEC (1) MCT (1) MMEF (1) Michael Cloppert (1) Ministério da Defesa (1) Netwtiness (1) OVAL (1) PL84/99 (1) RH2.5 (1) RNP (1) SDDFJ (1) SbSeg (1) Seccubus (1) Stratfor (1) TED (1) TJX (1) TV5 (1) TV5Monde (1) Tallinn (1) USCyberPatriot (1) USSTRATCOM (1) VERIS (1) VRT (1) WPS (1) WiPhire (1) Wifi Protected Setup (1) Windows10 (1) XMLHttpRequest (1) YARA (1) a5/1 (1) a5/3 (1) active defense (1) adeona (1) adhd (1) aes (1) afflib (1) akamai (1) alemanha (1) ambev (1) angler (1) anti-theft (1) antisec (1) anubisnetworks (1) apt (1) apwg (1) aquisição (1) arbor (1) armoring (1) artefatos (1) artillery (1) asprox (1) assinaturas (1) atenção seletiva (1) attack (1) aurora (1) australia (1) autonomous systems (1) avg (1) avi rubin (1) avware (1) awards (1) baixaki (1) bash (1) bbc (1) bear trap (1) belkasoft (1) bgp (1) birthday attack (1) bitlocker (1) black tulip (1) blackhat seo (1) blacklist (1) blind sql injection (1) bluepex (1) bluepill (1) breaking point (1) bug (1) bulk_extractor (1) byod (1) c2c (1) capacidade (1) carbon black (1) careto (1) carnivore (1) cartão de crédito (1) cbs (1) cellebrite (1) celular (1) centera (1) cerberus (1) certificações (1) cheat sheet (1) chip (1) chris paget (1) chromium (1) citrix (1) clean pipe (1) cliff stoll (1) cloudfare (1) cloudflare (1) cloudshield (1) cnasi (1) cnet (1) cnn (1) codenomicon (1) coleta (1) comodo (1) comodobr (1) compliance (1) comsic (1) convenção de budapeste (1) convergence (1) copa do mundo (1) coreia do norte (1) corey johnson (1) cpbr (1) crime na rede (1) crise (1) cristine hoepers (1) cuckoo (1) cyberattack (1) cyberbunker (1) daemonlogger (1) dam (1) dancho danchev (1) darkmarket (1) dcom (1) decaf (1) decaf v2 (1) decloack (1) deepweb (1) defcon (1) deutche telekom (1) dfrws (1) digitask (1) dimmit (1) diário oficial (1) dnsbl (1) dnssec (1) dou (1) downadup (1) drdos (1) drwxr (1) dsd (1) dumpcap (1) dumpit (1) duqu (1) e-evidence (1) ediscovery (1) eff (1) elcomsoft (1) emc (1) emprego (1) energia (1) enigma (1) entrevista (1) escola nacional de defesa cibernetica (1) eset (1) esteganografia (1) estonia (1) estratégia (1) etld (1) europa (1) eventos (1) evil maid (1) evilgrade (1) exercito (1) exploit-db (1) exportação (1) extorsão (1) f-secure (1) falso positivo (1) fantastico (1) fatal error (1) fecomercio (1) fernando carbone (1) ff4 (1) finlândia (1) flame (1) flexispy (1) foremost (1) forense de vídeo (1) forensic focus (1) forensic magazine (1) forensics (1) forensics.wiki.br (1) forensicswiki (1) força bruta (1) frança (1) full disk encryption (1) g1 (1) gauss (1) gcih (1) ghostnet (1) globo (1) gmail (1) gpcode (1) gpl (1) gps (1) grampo (1) guardium (1) guerra (1) guilherme venere (1) hack (1) hackerazzi (1) hackingteam (1) hakin9 (1) hardening (1) harlan carvey (1) hash (1) helix (1) hitler (1) holanda (1) honeynet (1) honeypot (1) hope (1) hosts (1) hotmail (1) httpry (1) iPhoneTracker (1) idefense (1) ig (1) impressoras (1) india (1) info exame (1) insecure maganize (1) intenção (1) interpol (1) interview (1) into the boxes (1) investimento (1) ioerror (1) iphone forensics (1) ironport (1) isc2 (1) israel (1) j2ee (1) jacomo dimmit (1) jailbreak (1) javascript (1) jesse kornblum (1) jotti (1) junho 2008 (1) kaminsky (1) kasumi (1) kgb (1) kits (1) klaus steding-jessen (1) kntools (1) kraken (1) langner (1) lime (1) limites (1) lista (1) lm (1) locaweb (1) lockheed martin (1) lynis (1) lógica (1) mac memory reader (1) mac memoryze (1) macosx (1) magic lantern (1) map (1) marcapasso (1) marcelo caiado (1) marcos ferrari (1) mawlare (1) mbr (1) mcafee (1) mcgraw (1) memscript (1) metasploitable (1) mindmap (1) mit (1) mitigação (1) mitm (1) moonsols (1) moxie (1) mrtg (1) ms08-033 (1) nac (1) nessus (1) netcontinuum (1) netflow (1) networking (1) ngrep (1) nit (1) nmap (1) norma (1) norse (1) notebook (1) ntlm (1) ntop (1) ntp (1) nuclear (1) obama (1) oi (1) oisf (1) oiss (1) olimpiadas (1) openbts (1) openvas (1) opm (1) oportunidade (1) oracle (1) orkut (1) otp (1) owasp (1) packers (1) panda (1) pattern matching (1) payback (1) pcre (1) pedofilia (1) pentesting (1) perforce (1) pericia (1) perl (1) perícia (1) pfsense (1) pgp disk (1) phonecrypt (1) pki (1) ploks (1) poisoning attack (1) policia civil (1) polypack (1) port knocking (1) português (1) post-mortem (1) postgres (1) powershell (1) prefeitura (1) premiação (1) preparação (1) princeton (1) provedores (1) ps3 (1) psn (1) psyb0t (1) pushpin (1) pwn2own (1) pymail (1) quebra de sigilo (1) r2d2 (1) rainbow tables (1) rar (1) realengo (1) reação (1) record (1) referência (1) regex (1) registry viewer (1) regulamentação (1) remnux (1) renato maia (1) renault (1) replay (1) reversing labs (1) roi (1) rootkit (1) router (1) rpc (1) ruby (1) sanitização (1) santoku (1) sc magazine (1) scada (1) scanner (1) scm (1) secerno (1) second life (1) security (1) securityonion (1) senasic (1) sentrigo (1) sep (1) sequestro de dados (1) sha1 (1) shadowserver (1) shmoocon (1) siemens (1) sites (1) skorobogatov (1) slideshare (1) smartcard (1) snapcell (1) software (1) sotirov (1) sp (1) spamhaus (1) spidertrap (1) squid (1) sri (1) ssdeep (1) sseguranca (1) sslstrip (1) sting (1) stj (1) street view (1) sucuri (1) superinteressante (1) são paulo (1) t-mobile (1) takedown (1) teamcymru (1) technosecurity (1) telefônica (1) terra (1) terrorismo (1) timeline (1) tizor (1) tls (1) token (1) topcell gsm (1) tresor (1) trustwave (1) tse (1) turquia (1) txtBBSpy (1) umass (1) unix (1) urna eletrônica (1) us-cert (1) usenix (1) userassist (1) vazamentos (1) venda de senhas (1) venere (1) verdasys (1) verisign (1) videntifier (1) visualização (1) visualize (1) vivo (1) vm (1) votação (1) wargaming (1) wasc (1) web 2.0 (1) weblabyrinth (1) websense (1) whitelisting (1) whois (1) wigle (1) win32dd (1) winacq (1) windbg (1) windd (1) winifixer (1) wipe (1) wired (1) wireshark (1) wlan (1) wordpress (1) wrf (1) xerxes (1) xp (1) zdi (1) zlob (1)