Temas sugeridos a desarrollar para exposición

Si encuentras alguna noticia del desarrollo interno en los sistemas operativos, seguramente será un tema de lo más interesante para que presentes. Y si bien las ligas que aquí presento son relativas a Linux, esto es por mi deformación profesional. ¡Toda nota relacionada a otros sistemas operativos es más que bienvenida!

Algunos recursos:

• Linux Weekly News es un sitio de noticias técnicas, de temática bastante variada, pero con mucho contenido relacionado al desarrollo del núcleo de Linux. Su editor, Jonathan Corbet, se ha dedicado a explicar –con una tremenda velocidad y claridad– los distintos conceptos que se manejan al interior del desarrollo tan pronto como aparecen.

  Las últimas noticias de LWN pueden estar limitadas sólo para los subscriptores, pero todo lo que tiene más de (me parece) un mes de publicado está disponible públicamente. Yo soy subscriptor de LWN, por lo que si les interesa un tema del cual sólo pueden ver el resumen, indíquenmelo y con gusto se los envío completo.

  • The Linux Storage, Filesystem and Memory Management Summit

    Hay un congreso anual dedicado al desarrollo, precisamente, de los ejes que llevan nuestro curso. Las presentaciones en este congreso, claro está, son de alto contenido técnico — Pero son muy seguibles, y les harán ver claramente el estado del arte y las tendencias a futuro, en Linux y en otros sistemas operativos, incluso en la relación con programas en espacio de usuario.

    Uno de los documentadores/comentaristas de las presentaciones de este congreso es, nuevamente, Jonathan Corbet, en LWN. Aquí tienen las ligas a la información de los últimos años:

    • 2019
    • 2018
    • 2017
    • 2016
    • 2014
    • 2013
    • 2012: Día 1, Día 2
    • 2011: Día 1, Día 2
    • 2010: Día 1, Día 2, Notas
    • 2009: Día 1, Día 2, Notas
    • 2008: Reseña en Usenix
    • 2007: Reseña en Usenix

El 23 de febrero de 2017 un equipo de investigadores del Centrum Wiskunde & Informatica, trabajando en conjunto con el grupo de investigación en seguridad de Google anunció que lograron generar una colisión en SHA1 entre dos documentos arbitrarios. ¿Qué significa esto?

SHA1 (Secure Hash Algorithm 1) es un estándar de función digestora aprobado por el NIST en 1995. Una función digestora (o, más corto, hash) toma por entrada una cadena de caracteres de longitud arbitraria, y emite una cadena de un tamaño fijo. Un punto muy importante para cualquier función que se busque para este fin es que su salida esté homogéneamente distribuida sobre todo el espacio definido, y que sea computacionalmente inalcanzable encontrar dos documentos diferentes que generen la misma cadena resultante — Eso es conocido como colisión.

¿Qué implicaciones tiene esta colisión? ¿Qué tanto tenemos que preocuparnos? ¿Cómo afecta esto a los sistemas operativos?

Información más a fondo, y ángulos que podrían desarrollar:

• Los autores registraron el dominio SHAttered.io (en inglés, to shatter significa romper, quebrantar, destruir. Este sitio contiene la información básica, fácil de comprender acerca del ataque.
• El artículo en que describen a fondo el trabajo realizado, The first collision for full SHA-1 (Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov), presenta la historia de este tipo de ataques, partiendo de una revisión histórica de los hitos parciales que llevaron a esto
• La sección 6 del artícuo presenta detalles acerca de la computación de la colisión. El programa generado es necesariamente masivamente paralelizado (los ataques requieren más de 6500 años-CPU para colisiones parciales). ¿Cómo se maneja ese nivel de paralelismo/
• Git utiliza ampliamente al SHA1 para representar la información. ¿Qué impacto tiene esto para el futuro de Git?
  • ¿Cómo está formado un commit en Git?

El modelo de cómputo distribuído basado en una malla o grid es muy flexible, y lo han adoptado proyectos de todo tipo. Pueden presentar a algunos de estos proyectos: ¿Qué es lo que se distribuye? ¿Cómo se paquetiza la información? ¿Cómo se re-agrega? ¿Qué tanto costo computacional adicional significa el separar en estos paquetes a la información?

Se puede emplear un modelo grid con participantes conocidos, con una membresía predeterminada, pero muchos proyectos lo abren a participación pública. ¿Hay consideraciones de seguridad a tomar en cuenta?

Hay una propuesta que podría ser aceptada en Linux para un modelo de paralelismo intermedio entre NUMA y cómputo distribuído, al que le llaman informalmente Popcorn Linux (y un poco más formalmente, "modelo de ejecución distribuída de hilos). Hay un buen texto que lo presenta de forma resumida:

https://lwn.net/SubscriberLink/819237/1acef28ea9f68bb8/

Pueden presentar qué atractivos o problemas podrían plantearse a partir de esta propuesta. No es demasiado distinto de otra que se popularizó hace varios años, OpenMosix.

Tras muchos años (¿décadas?) de encontrar gran resistencia por parte de la industria, al día de hoy buena parte de las computadoras nuevas vienen con el módulo de plataforma confiable (Trusted Platform Module) activo. Este polémico módulo implementa verificación de la integridad del sistema operativo, evitando que un ataque (sea un virus o un agente hostil) ejecute código que altere la operación del sistema operativo o incluso ejecute antes de éste y lo envuelva (por ejemplo, en un esquema de virtualización).

TPM, sin embargo, también evita que el dueño de una computadora la use como él quiera, teniendo que ejecutar únicamente los sistemas operativos aprobados o firmados por el fabricante.

Hay mucho que se puede decir acerca de TPM. ¿Cuál es tu planteamiento?

Sugiero como lectura para preparar este trabajo los varios artículos en el blog del desarrollador Matthew Garrett, particularmente entre septiembre del 2011 y mayo del 2013. Garrett lidereó la alternativa que al día de hoy más se usa para poder iniciar Linux en un sistema bajo TPM; tiene decenas de artículos desde muy descriptivos y generales hasta técnicos y específicos a puntitos particulares. Hay otro artículo interesante al respecto, de Jonathan Corbet (septiembre 2013): BSD-style securelevel comes to Linux — Again. Este artículo es de acceso restringido a subscriptores de LWN, pero si les interesa desarrollar el tema, les doy una copia. Explica con bastante detalle cómo es que se plantea implementar el nivel de protección que busca ofrecer TPM desde un sistema Linux.

Al hablar de virtualización, sea asistida por hardware o paravirtualización, varias voces se han levantado, indicando que ejecutar un sistema operativo completo dentro de una máquina virtual es un desperdicio de recursos. A fin de cuentas, si el sistema operativo típico a correr dentro de una máquina virtual en el CP del S/360 de IBM, hace más de 40 años, era un sistema sencillo, interactivo y monousuario (CMS), ¿por qué no repetir la experiencia?

Un ejemplo de sistema mínimo fue presentado en septiembre de 2013: OSv. Busca no implementar los subsistemas innecesarios de un Linux tradicional, pero permitir la ejecución de varios de los procesos más comunes en una máquina virtual. Pueden buscar al respecto:

• Anuncio en Slashdot: /New operating system seeks to replace Linux in the cloud
• Presentación del proyecto, del congreso CloudOpen
• Artículo respecto al lanzamiento de OSv en The Register
• Depósito Git del código de OSv en GitHub

Algunos puntos que podrían desarrollar:

• ¿Qué gana OSv y otros proyectos por el estilo? ¿Qué pierden?
• ¿Cómo ha avanzado la adopción de estas ideas?
• ¿Qué le agrega o quita a la complejidad de la administración de sistemas?
• ¿Qué significa esto para nuestra carrera/futuro profesional? ¿Hay de nuevo espacio para desarrollar sistemas operativos novedosos, o serán unos pocos los que llenarán el nicho?

La arquitectura x86 (32 y 64 bits) ofrece un modelo de seguridad basado en cuatro anillos de ejecución de código.

No, no son cuatro. Son cinco. ¡Ah, no! Son seis. Pero sólo cuatro están disponibles para el sistema operativo.

Una presentación en el congreso Black Hat 2015 presenta los niveles de protección -1 y -2, y cómo –por una falta de verificación en el diseño de los CPUs– hacer un ataque que otorga control absoluto sobre la computadora.

Pero absoluto en los términos más absolutos. Absoluto e invisible para el CPU e incluso para el hipervisor.

Este tema puede abordarse de forma meramente descriptiva, o ir entrando a los detalles muy profundamente técnicos. Revisen:

• Intel left a fascinating security flaw in its chips for 16 years — here's how to exploit it: Artículo bastante digerible y sencillo de entender en The Register presentando el problema
• The Memory Sinkhole: An architectural privilege escalation vulnerability: Presentación hecha para el congreso Black Hat 2015, en que explica –ilustrando primero con esquemas, luego con código– y demuestra el problema.

Un tema no directamente relacionado con el temario, pero que puede ligarse con varios conceptos mencionados en esta unidad, es la gestión del arranque del sistema: Una vez que el núcleo carga y hace un recorrido básico del hardware creándose un mapa de cómo es el sistema en que está corriendo, tiene que llevar el equipo a un estado funcional para sus usuarios. ¿Cómo ocurre esto?

Tradicionalmente, los sistemas Unix se dividían entre dos filosofías de arranque (los sistemas SysV y los sistemas BSD). Pero la realidad del cómputo ha cambiado con el tiempo. En los últimos años, y si bien hay varias otras propuestas, la mayor parte de las distribuciones Linux se han decantado por un sistema llamado systemd, desarrollado originalmente por RedHat.

¿Cuáles son los planteamientos básicos de los arranques tipo SysV y tipo BSD? ¿A qué tipo de cambios en la realidad me refiero? ¿Por qué los esquemas tradicionales se están quedando cortos? ¿En qué se parecen y en qué se diferencian systemd y upstart? ¿Qué ventajas y desventajas conllevan?

En clase abordamos mecanismos para sincronización utilizando primitivas bloqueantes, como los mutexes sencillos, los semáforos o (a mucho menor profundidad) las variables de condición. Pero cuando programamos al nivel del sistema operativo, a veces hay casos en que hace falta un tiempo de respuesta menor que el que imponen nuestras ya queridas primitivas — o a veces, que sencillamente no hay ninguna capa que nos pueda brindar esa abstracción.

En el kernel hace falta a veces programar con algoritmos libres de bloqueos. En febrero y marzo de 2021, Paolo Bonzini presentó una serie de artículos acerca de algoritmos libres de bloqueos en LWN.

Esta unidad es en la que más nos dedicaremos a escribir y analizar código. Si bien para presentar como casos de ejemplo presentamos a cuatro de los casos clásicos (el problema productor-consumidor, el problema lectores-escritores, la cena de los filósofos y los fumadores compulsivos), hay muchos otros casos ampliamente analizados.

Pueden presentar otro de los casos presentados en el libro recomendado como referencia, The little book of semaphores (Allan Downey, 2008), o de alguna otra fuente.

Los sistemas operativos modernos buscan exprimir hasta el último pedacito de rendimiento. Para estudiar cómo lo hacen, podemos asomarnos a las discusiones (y a la implementación) de Linux. Los últimos diez años han sido de fuerte profesionalización y optimización.

Para el tema de planificación de procesos, un punto muy importante fue la introducción del kernel prevenible (o interrumpible), en 2004.

¿Qué significa que el núcleo mismo del sistema operativo puede ser interrumpido? ¿Quién lo puede interrumpir? ¿Qué consecuencias tuvo esto, en complejidad de código y en velocidad?

Pueden basarse para la preparación de este tema en un interesante reporte de NIST (Instituto Nacional de Estándares y Tecnología) de diciembre del 2002, Introduction to Linux for Real-Time Control: Introductory Guidelines and Reference for Control Engineers and Managers. Detalla muy bien cuáles son los requisitos (y las razones detrás de dichos requisitos) para la implementación de sistemas operativos de tiempo real, e incluye una revisión del panorama de este campo, muy interesante y muy buen recurso para construir desde ahí.

En Linux, desde la versión 2.6.23, se usa un mecanismo de planificación llamado Planificador Completamente Justo (Completely Fair Scheduler). Sin embargo, para responder a procesos específicos con necesidades diferentes, Linux mantiene también clases de planificación independientes, las primeras de ellas más parecidas a los mecanismos simples vistos en clase: SCHED_RR y SCHED_FIFO.

En marzo del 2014, con el anuncio de la versión 3.14 del kernel, fue agregada la clase SCHED_DEADLINE, principalmente pensada para dar soporte a las necesidades de tiempo real. Esta opera bajo una lógica EDF (Primer Plazo Primero, Earliest Deadline First).

Además de exponer este algoritmo, quisiera que expusieran cómo el sistema da soporte a la mezcla de distintas clases de planificación en un mismo sistema vivo, y que hicieran un breve análisis acerca de qué tanto EDF (o SCHED_DEADLINE, esta implementación específica) es tiempo real suave o duro.

Algunas ligas al respecto:

• Artículo en LWN de diciembre de 2013 anticipando la inclusión de SCHED_DEADLINE, que presenta los conceptos, e incluye una discusión al respecto que puede resultarles interesante y útil
• La página de la clase de planificación SCHED_DEADLINE en Wikipedia
• La documentación de SCHED_DEADLINE en el núcleo de Linux

La realidad que presentamos en la primer unidad del curso respecto al multiprocesamiento simétrico como fuertemente dominante en relación a los sistemas NUMA se mantiene cierta… Pero va cambiando rápidamente, y los sistemas NUMA son cada vez más comunes.

Claro está, la popularización de los sistemas NUMA tiene un alto impacto en cómo se manejan los esquemas de administración de memoria.

En el número de septiembre del 2013 de la revista Communications of the ACM aparece un artículo corto, conciso y bastante interesante, de Cristoph Lameter: An overview of non-uniform memory access. Sugiero emplearlo como punto de partida.

Este tema queda en un estado intermedio entre nuestra materia y la de Compiladores.

Cuando vamos convirtiendo un programa escrito por un humano en código ejecutable, no sólo tenemos que convertir las instrucciones y proveer las abstracciones mínimas — También hay que preparar al código para poder ser reubicado en la memoria.

El proceso de cargado se refiere a cómo la imagen binaria del programa que está grabada en un medio de almacenamiento es modificada al llevarse a memoria para adecuarse al espacio que le asigna el sistema operativo; el proceso de ligado es cómo se le adosan las bibliotecas compartidas.

En este proceso entran temas como la gestión de memoria compartida, las indicaciones al compilador para generar código independiente de su posición, etc.

La complejidad que tiene el manejo de la memoria caché es alta, pero es muy interesante. ¿Pueden detallar más de lo visto en clase sobre su funcionamiento?

Pueden resultar de su interés algunos emuladores; pueden utilizarlos como material de apoyo durante su exposición: revisen los desarrollados por distintas universidades:

• Universidad Tecnológica Nanyang de Singapúr
• Universidad Estatal de Sonoma
• Universidad de Massachusetts Amherst (incluye explicación y simulación por separado de distintos aspectos)
• Universidad de Michigan (incluye programas ejemplo a seguir)
• Universidad de Washington

En un entorno multiprocesador, el acceso concurrente a las mismas posiciones de memoria se vuelve muy complicado — Por decir lo menos. Los distintos niveles de memoria caché tienen que sincronizar su operación (a altísima velocidad) y permitir que avancen los procesos compartiendo datos.

Hay varios mecanismos para mantener la coherencia. Algunas líneas para comenzar tu búsqueda pueden ser, para computadoras razonablemente pequeñas, los mecanismos fisgones (snoopy) de invalidación y de actualización, y para equipos más grandes, los mecanismos por hardware de directorio; puedes tambíén comenzar buscando los protocolos MSI, MESI (Illinois), MOSI (Berkeley), MOESI y MESIF.

El 7 de abril del 2014 fue dado a conocer un fallo en la biblioteca criptográfica OpenSSL, particularmente en la rutina que implementa el Heartbeat. Dada la base instalada de OpenSSL, y lo sensible de la información que expone al atacante, este puede ser uno de los ataques con mayor impacto registado.

Algunas ligas al respecto:

• http://heartbleed.com/ Presenta toda la información principal de este fallo. Como nota lateral, es muy poco común que un fallo termine registrando una página de este modo — ¿Será por el impacto esperado?
• http://www.theregister.co.uk/2014/04/09/heartbleed_explained/ Un muy buen artículo delineando la mecánica de este fallo
• http://blog.erratasec.com/2014/04/why-heartbleed-doesnt-leak-private-key.html Ojo, esta liga omite algunos datos importantes, por lo que juzgo que su análisis es erróneo. Sin embargo, tiene una explicación muy buena del problema paso a paso.
• http://seclists.org/fulldisclosure/2014/Apr/ La lista de correo Full Disclosure es fundamental para cualquier profesional de la seguridad. Busca en este mes la discusión relacionada con esta vulnerabilidad.

Esta unidad es probablemente la que mejor nos permite ver directamente la relación entre los temas cubiertos y su manejo en un sistema operativo actual. Puedes preparar una exposición de cómo reacciona un sistema operativo de propósito general ante cambios en los distintos valores y umbrales, cuáles serían las condiciones límite, qué comportamientos esperaríamos, cómo es la interfaz al administrador del sistema, etcétera.

Puedes hacer esta comparación con el o los sistemas operativos que elijas (y la comparación entre sistemas operativos distintos seguramente resultará también muy interesante); en el caso de Linux, te sugiero revisar la documentación de los parámetros de sysctl relativos a la memoria virtual. Puedes encontrarlos en:

https://github.com/torvalds/linux/blob/master/Documentation/sysctl/vm.txt

Uno de los últimos temas que vemos en esta unidad en clase es el del conjunto activo. Este tema resulta de gran importancia al considerarnos desarrolladores de aplicaciones, si nos interesa lograr un buen rendimiento. ¿Cómo puede el sistema operativo detectar y predecir el conjunto activo de un proceso para no jugarle en contra? LWN presentó en marzo de 2020 el interesante texto Working-set protection for anonymous pages abordando el tema.

En clase exponemos los principales puntos de los medios de estado sólido o no rotativos, apuntando apenas hacia cómo podrían estos aprovecharse mejor.

¿Qué sistemas de archivos están mejor afinados para operar con medios Flash? ¿Cuáles son los principales obstáculos para que gocen de una mayor adopción?

Una de las características que ofrecen varios sistemas operativos de última generación es la desduplicación: La detección de sectores idénticos pertenecientes a más de un archivo, para evitar repetirlos varias veces en el disco (es un fenómeno que ocurre mucho más de lo que esperaríamos). Esta detección se realiza típicamente por medio de hashes criptográficos.

¿Cómo opera un poco más a detalle este mecanismo? ¿Qué tan confiable es? (vamos, ¿se puede utilizar ya en sistemas en producción?) ¿Qué pasa con el espacio libre reportado al sistema? ¿No se cae en riesgos de sobrecomprometimiento (overcommit)? ¿Qué es la desduplicación en línea y la desduplicación fuera de línea (online deduplication, offline deduplication)? ¿Cómo opera el hash criptográfico? ¿Hay veces que resulte insuficiente? ¿Qué alternativas hay?

Como referencia informal al respecto, sugiero leer el hilo de discusión al respecto en la lista de DebConf (el congreso de Debian).

• Desarrollar a partir (o en vez) de los temas de NFS, SMB, AFS que están en el material del curso
• Avanzar hacia sistemas más modernos — Ejemplos: GlusterFS (RedHat), Amazon (S3), CEPH