Capítulo 6 — Estruturas discretas
Mapa da aula
Aula 06 publicada. Mapa, exemplo, EX016.
flowchart TD
N0["6.1 Conjuntos e relações"]
N1["6.2 Grafos"]
N2["6.3 Busca em grafos"]
N3["6.4 Contagem"]
N4["Síntese"]
N0 --> N1 --> N2 --> N3 --> N4
N4 --> EX["Exemplo resolvido"]
EX --> Q["Exercício EX016"]
Desenho lógico
flowchart LR
N0["6.1 Conjuntos e relações"]
N1["6.2 Grafos"]
N2["6.3 Busca em grafos"]
N3["6.4 Contagem"]
N4["Síntese"]
N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX016"]
[6.1 Conjuntos e relações]
|
v
[6.2 Grafos]
|
v
[6.3 Busca em grafos]
|
v
[6.4 Contagem]
|
v
[Síntese]
|
v
[Exemplo resolvido] --> [Exercício EX016]
Objetivos de aprendizagem
Você vai (1) usar conjuntos, relações e grafos para modelar sistemas; (2) expressar regras de acesso como relações e verificá-las; (3) encontrar, num grafo, caminhos de entradas não confiáveis até ações sensíveis; e (4) contar possibilidades para julgar se a força bruta é viável.
6.1 Conjuntos e relações
Uma regra de controle de acesso é uma relação entre sujeitos, ações e objetos: (paciente P, marcar, a própria consulta) é permitido; (paciente P, ver, registro de outro paciente) não é. Escrever as regras como conjuntos de triplas permitidas as torna verificáveis por programa e expõe casos ausentes. Uma vez que as regras são um conjunto, um programa pode verificar cada pedido contra ele e listar qualquer ação que não tenha regra alguma. A primeira tentativa de Rina descobriu que "cancelar" não tinha regra para pacientes que cancelassem a consulta de outra pessoa, algo que a política em prosa simplesmente não mencionava. Acrescentar uma negação explícita fechou a lacuna, e o conjunto passou a ser a referência para as verificações de marcação dela.
6.2 Grafos
Um grafo tem nós e arestas. Desenhe um sistema de IA como um grafo dirigido: usuário → chatbot → modelo → ferramenta de agendamento → sistema de agendamento, mais repositório de documentos → modelo. Um caminho de um nó não confiável (uma página web pública, um documento enviado) até um nó sensível (a ferramenta de agendamento) é uma rota potencial de ataque. A injeção indireta de prompt segue exatamente esse tipo de caminho (Greshake et al., arXiv:2302.12173). Desenhar o grafo tornou visível uma aresta que o documento de arquitetura não havia registrado: organizações parceiras enviam documentos para o repositório que o modelo lê.
6.3 Busca em grafos
A busca em largura encontra todos os nós alcançáveis a partir de um nó inicial. Executá-la a partir de cada nó não confiável e verificar se os nós sensíveis são alcançáveis é uma verificação de arquitetura simples e automatizável. O custo cresce com o número de nós e arestas, então mesmo sistemas grandes podem ser verificados em segundos. O valor está em manter o grafo exato: uma nova origem de envios ou uma nova ferramenta deve ser acrescentada assim que existir, ou a busca relatará um resultado limpo para um sistema que já não corresponde a ele. Rina reexecuta a verificação sempre que o mapa de arquitetura muda e guarda a saída junto do mapa.
6.4 Contagem
Se um código de marcação tem 6 dígitos, há 10⁶ possibilidades; a 10 tentativas por segundo, um atacante precisa de cerca de 28 horas para testar todas, então limites de taxa e bloqueios importam. A contagem transforma intuição em números. Com um bloqueio após cinco tentativas erradas, um atacante tem cinco tentativas por conta em vez de um milhão, uma chance de sucesso de cinco em um milhão. A mesma aritmética vale para adivinhar identificadores de pacientes pelo chatbot: se os identificadores são curtos e sequenciais, a enumeração é barata. Rina inclui esses cálculos em suas revisões, para que os ajustes de limite de taxa se apoiem em números, e não em impressões.
6.5 Exemplo resolvido (caso sintético da LCH)
Rina listou os nós e as arestas do Ask Lumen e executou à mão uma verificação de alcançabilidade. Duas origens não confiáveis alcançavam a ferramenta de agendamento: o chat dos pacientes (esperado, controlado por autenticação) e os envios de documentos das clínicas por organizações parceiras (inesperado). Os envios dos parceiros podiam conter texto com aparência de instrução que o modelo talvez seguisse. A LCH acrescentou revisão para documentos de parceiros e manteve a ferramenta de agendamento atrás de uma verificação de política vinculada ao paciente conectado. O segundo caminho explica por que os dois controles foram mantidos, em vez de um só: a revisão reduz a chance de texto hostil, e a verificação de política limita seu efeito.
6.6 Erros e limites
Três erros são comuns: regras de acesso escritas apenas em prosa; grafos que omitem repositórios de dados e envios; e ignorar a rapidez com que computadores enumeram possibilidades. Regras em prosa deixam casos indefinidos, como mostrou a regra de cancelamento ausente. Grafos que omitem envios e repositórios de dados deixam escapar justamente a rota pela qual a injeção indireta de prompt chega a uma ferramenta. Subestimar a velocidade de enumeração leva a limites fracos para códigos e identificadores; um código de seis dígitos sem limite de taxa cai em cerca de um dia a apenas dez tentativas por segundo, e muito mais rápido com mais.
Exercícios
- EX016 — Relação. Escreva três triplas permitidas e duas proibidas para o Ask Lumen. Rubrica: 3 = cinco triplas sensatas; 2 = quatro; 1 = duas; 0 = nenhuma.
- EX017 — Caminhos. Nomeie o caminho inesperado que Rina encontrou e um controle. Rubrica: 3 = envios de parceiros → modelo → agendamento; revisão mais política vinculada ao paciente; 2 = só o caminho; 1 = vago; 0 = nenhum.
- EX018 — Contagem. Um código de 4 dígitos a 5 tentativas por segundo: tempo no pior caso? Rubrica: 3 = 10,000/5 = 2,000 s ≈ 33 min; 2 = deslize; 1 = método; 0 = nenhum.
Síntese
As estruturas discretas oferecem ferramentas exatas — relações para regras, grafos para fluxo de dados, contagem para viabilidade — que tornam visíveis as fraquezas de sistemas de IA.
Continue estudando — capítulo 06 de 40
← Capítulo 05 (rascunho) · Índice de capítulos do curso · Capítulo 07 (rascunho) →