How should we automatically rebuild immutable infrastructure when new packages are available?
Part of adopting the Immutable Infrastructure Pattern is decomposing your system into small manageable pieces that can move through CI/CD Pipeline very quickly, this means that OS patches can be done quickly and in a controlled manner.  I often see clients ending up with a halfway house where infrastructure is mostly immutable.

However, there are a few approaches to this which I have used in large-scale deployments of cloud architecture, typically I implement more than one as part of a Defense in Depth strategy:


Security Information and Event Management (SIEM): These products, for example, LogRhythm Security Intelligence Platform and more generic products such as ElasticStack take feeds from the operating system, which includes the output from a frequent check for updates.  The trick here is to get the information about what to patch quickly and automatically to inform decisions about when to roll those through your pipeline.
Vulnerability Management systems are more tailored than SIEM in that they are only focusing on vulnerabilities across the system so could catch issues with libraries installed as part of the software deployed to the system but not managed by the Operating System.  This might highlight vulnerabilities for which there is no patch (yet... hopefully).
Dependency Check tools form part of your pipeline and can be configured to fail the build if check-ins add vulnerabilities, this also works if a new vulnerability is added to the tool since the last check-in.