Eu acredito que você tenha que remover o apparmor antes de instalar o SELinux:
sudo apt-get remove apparmor
De acordo com a página wiki do SELinux :
% bl0ck_qu0te%
Reinicie
Durante o desligamento, todos os arquivos no sistema serão rotulados. Isso pode levar algum tempo dependendo de quantos arquivos você possui e da velocidade do disco.
Uma pesquisa usando apt-cache search
ativa esses pacotes:
postgresql-contrib-9.4 - additional facilities for PostgreSQL
ruby-selinux - Ruby bindings to SELinux shared libraries
checkpolicy - SELinux policy compiler
debian-handbook - reference book for Debian users and system administrators
joe-jupp - reimplement the joe Debian package using jupp
jupp - user friendly full screen text editor
libseaudit-dev - Security Enhanced Linux audit message parser development
libseaudit4 - Security Enhanced Linux audit message parsing library
libsefs-dev - Security Enhanced Linux file context management development
libsefs4 - Security Enhanced Linux file context management
libsetools-java - SETools Java bindings (architecture-independent)
libsetools-tcl - SETools Tcl bindings
libtomoyotools3 - lightweight Linux Mandatory Access Control system - library
policycoreutils - SELinux core policy utilities
python-selinux - Python bindings to SELinux shared libraries
python-semanage - Python bindings for SELinux policy management
python-sepolgen - Python module used in SELinux policy generation
python-sepolicy - Python binding for SELinux Policy Analyses
python-setools - SETools Python bindings
ruby-semanage - Ruby bindings to for SELinux policy management
selinux - Security-Enhanced Linux runtime support
selinux-basics - SELinux basic support
selinux-policy-default - Strict and Targeted variants of the SELinux policy
selinux-policy-dev - Headers from the SELinux reference policy for building modules
selinux-policy-doc - Documentation for the SELinux reference policy
selinux-policy-dummy - Empty Security-Enhanced Linux policy (dummy package)
selinux-policy-mls - MLS (Multi Level Security) variant of the SELinux policy
selinux-policy-src - Source of the SELinux reference policy for customization
selinux-policy-ubuntu - Security-Enhanced Linux Reference Policy
selinux-policy-ubuntu-dev - Security-Enhanced Linux Reference Policy Development Headers
selinux-policy-ubuntu-doc - Security-Enhanced Linux Reference Policy Documentation
selinux-utils - SELinux utility programs
setools - tools for Security Enhanced Linux policy analysis
setools-gui - GUI tools for Security Enhanced Linux policy analysis