Capítulo 6 — Estructuras discretas | Grado Seguridad de infraestructuras críticas y sectores

Aprendizaje gratuito y abierto para quienes desean proteger a las personas y la tecnología. No se necesita una cuenta para estudiar ni consultar las respuestas.

Mapa de la lección

Lección 06 publicada. Mapa, ejemplo, EX012.

flowchart TD
  N0["Resultados de aprendizaje y conexión"]
  N1["6.1 Conjuntos y relaciones"]
  N2["6.2 Lógica"]
  N3["6.3 Grafos"]
  N4["6.5 Actividad práctica"]
  N5["Síntesis del capítulo"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5
  N5 --> EX["Ejemplo resuelto"]
  EX --> Q["Ejercicio EX012"]

Dibujo lógico

flowchart LR
  N0["Resultados de aprendizaje y conexión"]
  N1["6.1 Conjuntos y relaciones"]
  N2["6.2 Lógica"]
  N3["6.3 Grafos"]
  N4["6.5 Actividad práctica"]
  N5["Síntesis del capítulo"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX012"]

[Resultados de aprendizaje y conexión]
    |
    v
[6.1 Conjuntos y relaciones]
    |
    v
[6.2 Lógica]
    |
    v
[6.3 Grafos]
    |
    v
[6.5 Actividad práctica]
    |
    v
[Síntesis del capítulo]
    |
    v
[Ejemplo resuelto] --> [Ejercicio EX012]

Resultados de aprendizaje y conexión

Después de este capítulo usted podrá (1) usar conjuntos y operaciones de conjuntos para razonar sobre inventarios y permisos; (2) escribir condiciones lógicas y comprobarlas con tablas de verdad; (3) modelar las dependencias entre servicios como un grafo dirigido y calcular qué resulta afectado cuando falla un nodo; y (4) reconocer cuándo es factible una comprobación exhaustiva y cuándo el número de estados la hace imposible. Se apoya en la programación del capítulo 3 y prepara el capítulo 13 (acceso), el capítulo 22 (dependencias) y el capítulo 28 (análisis de fallas).

6.1 Conjuntos y relaciones

Un conjunto es una colección de elementos distintos. Los dispositivos de la red clínica forman un conjunto $C$; los dispositivos que han superado el fin de su soporte forman un conjunto $U$; su intersección $C \cap U$ es el conjunto que hay que aislar primero. La unión $A \cup B$ reúne los elementos que están en cualquiera de los dos; la diferencia $A \setminus B$ conserva los elementos que están en $A$ pero no en $B$. El control de acceso es razonamiento con conjuntos: los permisos efectivos de un usuario son la unión de los permisos de sus roles, y una regla de separación de funciones dice que ciertos pares nunca deben estar ambos en esa unión (capítulo 13). Una relación conecta elementos de dos conjuntos: «el usuario u tiene el rol r», «el servicio s depende del servicio t». Muchas preguntas de seguridad son preguntas sobre relaciones: quién puede llegar a qué, qué depende de qué.

6.2 Lógica

Una proposición es verdadera o falsa. Las proposiciones se combinan con y ($\wedge$), o ($\vee$) y no ($\neg$). Una regla como «un pago superior a £10.000 solo se libera si lo crea una persona y lo aprueba otra distinta, o si es una transferencia de emergencia aprobada por dos directores» es una expresión lógica; escribirla formalmente deja al descubierto sus lagunas («¿y si quien lo crea también es director?»). Una tabla de verdad enumera todas las combinaciones de entradas; con $n$ entradas tiene $2^n$ filas. Con 4 entradas son 16 filas, algo fácil. Con 40 entradas son unas $10^{12}$ filas, imposibles de comprobar a mano, y por eso los sistemas complejos necesitan estructura, pruebas y argumentación en lugar de enumeración exhaustiva. Las leyes de De Morgan, $\neg(A \wedge B) \equiv \neg A \vee \neg B$, permiten reescribir las condiciones de «no permitido» como condiciones de «permitido» y comprobar que ambas dicen lo mismo.

6.3 Grafos

Un grafo es un conjunto de nodos y aristas. En un grafo dirigido, las aristas tienen dirección; escribimos $u \to v$ para indicar que «$v$ depende de $u$». A partir de un nodo que ha fallado, una búsqueda en anchura visita todos los nodos alcanzables siguiendo las aristas: ese conjunto es todo lo que puede resultar afectado. El número de nodos alcanzables desde un nodo es su alcance; los nodos con alto alcance son candidatos a protección o respaldo adicionales. Los grafos también dejan ver los puntos únicos de falla: nodos cuya eliminación desconecta servicios de lo que necesitan. El artículo clásico de Rinaldi, Peerenboom y Kelly describe las infraestructuras como interdependientes exactamente en este sentido: física, cibernética, geográfica y lógicamente (Rinaldi et al., 2001).

6.4 Ejemplo resuelto y Lab 3: dependencias del condado de Calder (sintético)

Este caso es sintético. La CRP trazó un primer mapa de dependencias: la subestación eléctrica alimenta las bombas de agua, el suministro de red del hospital, la central de telecomunicaciones y la señalización ferroviaria; la central de telecomunicaciones transporta el despacho, los pagos con tarjeta, la telemetría del agua y el archivo de imágenes en la nube del hospital.

# Lab 3 - cross-sector dependency closure on a directed graph (synthetic Calder County, offline)
from collections import deque
# edge u -> v means "v depends on u"
DEPENDS = {
    "grid-substation-N": ["water-pumps", "hospital-main", "telecom-exchange", "rail-signalling"],
    "telecom-exchange": ["dispatch-cad", "card-payments", "water-telemetry", "hospital-pacs-cloud"],
    "water-pumps": ["hospital-water"],
    "water-telemetry": ["water-pumps"],
    "dispatch-cad": ["ambulance-dispatch"],
    "hospital-main": [],
    "card-payments": ["fuel-retail"],
    "rail-signalling": [], "hospital-water": [], "hospital-pacs-cloud": [],
    "ambulance-dispatch": [], "fuel-retail": [],
}
def affected(start):
    seen, q = {start}, deque([start])
    while q:
        for v in DEPENDS.get(q.popleft(), []):
            if v not in seen:
                seen.add(v); q.append(v)
    return sorted(seen - {start})
for node in ("grid-substation-N", "telecom-exchange", "water-telemetry"):
    a = affected(node)
    print(f"{node}: {len(a)} affected -> {', '.join(a)}")
fan = sorted(((len(affected(n)), n) for n in DEPENDS), reverse=True)[:3]
print("highest reach:", fan)

Salida esperada:

grid-substation-N: 11 affected -> ambulance-dispatch, card-payments, dispatch-cad, fuel-retail, hospital-main, hospital-pacs-cloud, hospital-water, rail-signalling, telecom-exchange, water-pumps, water-telemetry
telecom-exchange: 8 affected -> ambulance-dispatch, card-payments, dispatch-cad, fuel-retail, hospital-pacs-cloud, hospital-water, water-pumps, water-telemetry
water-telemetry: 2 affected -> hospital-water, water-pumps
highest reach: [(11, 'grid-substation-N'), (8, 'telecom-exchange'), (2, 'water-telemetry')]

Lea el resultado con cuidado. El grafo dice puede resultar afectado, no fallará: ignora la energía de respaldo, el almacenamiento y la operación manual. Es deliberado: el primer mapa indica dónde mirar; el capítulo 22 añade el tiempo y la autonomía de respaldo. También revela una decisión de modelado: aquí las bombas de agua dependen de la telemetría solo si no pueden funcionar localmente. Cada arista es una afirmación que alguien debería poder justificar.

6.5 Actividad práctica

Añada una arista que crea que falta (por ejemplo, el agua del hospital depende de la planta de tratamiento, que depende de la subestación) y un camino alternativo (una segunda central de telecomunicaciones). Vuelva a calcular el alcance. Escriba tres frases sobre lo que el cambio muestra y lo que no muestra. Añadir «planta de tratamiento → agua del hospital» y «subestación → planta de tratamiento» aumenta aún más el alcance de la subestación, mientras que una segunda central no resta nada al recuento simple de alcanzabilidad: la búsqueda sigue marcando todos los nodos a los que puede llegar un solo camino. Esa es la limitación que EX012 le pide explicar, y es la razón para escribir de forma distinta las dependencias AND y OR.

6.6 Errores comunes y límites

Confundir la dirección de las aristas («depende de» frente a «suministra»); escriba la convención en la parte superior de cada diagrama.
Tratar la alcanzabilidad como certeza de falla.
Construir un grafo desde la visión de una sola organización: otros operadores conocen dependencias que usted ignora.
Intentar enumerar espacios de estados de tamaño exponencial.

En el Lab 3, la línea de convención edge u -> v means "v depends on u" es lo que hace legible el alcance de 11 nodos de la subestación; invertida, la misma lista afirmaría que la subestación depende de la venta minorista de combustible. Un alcance de 11 significa exposición, no falla, ya que el hospital tiene 72 horas de autonomía con sus generadores. El mapa es la primera visión de la CRP y carece de lo que saben los ingenieros de CW y de CPN. Y el argumento de la tabla de verdad escala en sentido contrario: 40 entradas binarias dan alrededor de un billón de filas.

Ejercicios — capítulo 6

EX011 — Conjuntos para la clasificación. Objetivo: usar operaciones de conjuntos. Entradas: C = {INF-01, INF-02, IMG-01, IMG-02, ADM-02}; U = {INF-02, IMG-01, IMG-02, LAB-01, ADM-02}; K (dispositivos con un defecto con explotación conocida) = {IMG-01, ADM-02}. Pasos: calcule $C \cap U$, $(C \cap U) \cap K$ y $U \setminus C$; diga sobre qué conjunto actuaría primero y por qué. Evidencia esperada: tres conjuntos y una razón. Rúbrica: 3 = todo correcto y prioridad para $(C \cap U) \cap K$ = {IMG-01, ADM-02}; 2 = un error; 1 = dos errores; 0 = nada.

EX012 — Un camino alternativo. Objetivo: ver cómo cambia el alcance con la redundancia. Entradas: el Lab 3. Pasos: modele que dispatch-cad también puede usar un enlace satelital independiente de la central, de modo que perder solo la central ya no detiene el despacho. Explique por qué una búsqueda simple de alcanzabilidad no puede expresarlo y proponga un cambio de modelado. Evidencia esperada: la explicación y la propuesta. Rúbrica: 3 = reconoce la dependencia OR (necesita uno cualquiera de varios proveedores) frente a la dependencia AND y propone nodos que requieren todas o alguna de sus entradas; 2 = solo reconoce el problema; 1 = edita las aristas de forma incorrecta; 0 = nada.

Síntesis del capítulo

Los conjuntos describen inventarios y permisos; la lógica hace que las reglas sean exactas y comprobables; los grafos hacen visibles y calculables las dependencias. Cada modelo responde a una pregunta más estrecha de lo que parece: la alcanzabilidad muestra exposición, no falla, y la comprobación exhaustiva solo funciona mientras el espacio de estados es pequeño.